当前位置：首页 > news >正文

代码随想录第二十一天|动态规划（5）

news 来源：原创 2024/9/20 11:47:01

LeetCode 198. 打家劫舍

LeetCode 213. 打家劫舍 II

LeetCode 337. 打家劫舍 III

总结

LeetCode 198. 打家劫舍

题目链接：LeetCode 198. 打家劫舍

思想：本题依旧是动态规划五步走。第一步确定dp数组及其下标含义，dp[i]代表的是偷窃第i家目前能获得的最高金额。关于递推公式的话，dp[i]的决定可以从第i-2房间来决定，当前的最高金额可以是dp[i-2]+nums[i]；其次就是不偷第i个房间，那么第i个房间能获得的最高金额可以由i-1获得，即dp[i-1]。所以递推公式就是dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。关于dp数组的初始化，根据递推公式，一个状态需要前两个状态的值，也就是说dp[0]和dp[1]需要初始化，dp[0]可以初始化为nums[0]，而dp[1]就初始化为max(nums[0],nums[1])，因为是求最大嘛。遍历顺序的话就从第二个房间遍历到最后一个房间就行了。

代码如下：

    int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}

时间复杂度：O(n)，空间复杂度：O(n)。

LeetCode 213. 打家劫舍 II

题目链接：LeetCode 213. 打家劫舍 II

思想：本题关于上题做了一些改进，现在头尾房子相连，所以关于动归五部曲的所有东西都可以不用变。而怎么避免首尾带来的相邻呢，可以只考虑首或只考虑尾，然后分别求一次动归，然后返回最大值。

代码如下：

    int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2);int result2 = robRange(nums, 1, nums.size() - 1);return max(result1, result2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}

时间复杂度：O(n)，空间复杂度：O(n)。

LeetCode 337. 打家劫舍 III

题目链接：LeetCode 337. 打家劫舍 III

思想：本题又换了，房间按照二叉树的样子排列，被偷的房子不能直线相连。这题不能采用上述一样的动归五部曲。得换一个方式。首先就是确定遍历树的方式，本题一定是后序遍历，因为要根据左右孩子的值来计算当前能获得的最高金额。如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）。

本题需要融合递归三部曲和动归五部曲，脑子有点小转不过来了，所以这里直接借用代码随想录的思想和讲解内容了。

确定递归函数的参数和返回值

这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。参数为当前节点，代码如下：

vector<int> robTree(TreeNode* cur) {

其实这里的返回数组就是dp数组。所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。所以本题dp数组就是一个长度为2的数组！那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？别忘了在递归的过程中，系统栈会保存每一层递归的参数。如果还不理解的话，就接着往下看，看到代码就理解了哈。

确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

if (cur == NULL) return vector<int>{0, 0};

这也相当于dp数组的初始化

确定遍历顺序

首先明确的是使用后序遍历。因为要通过递归函数的返回值来做下一步计算。通过递归左节点，得到左节点偷与不偷的金钱。通过递归右节点，得到右节点偷与不偷的金钱。

代码如下：

// 下标0：不偷，下标1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

代码如下：

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};

最终代码如下：

    int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int> {0,0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}

时间复杂度：O(n)，空间复杂度：O(logn)。