跨境电商开发软件_一键优化在哪里打开_旺道seo软件_大数据查询官网

第九章 动态规划 Part 07

今天是打家劫舍的一天，这个系列题目不算难，大家可以一口气拿下。

198. 打家劫舍

视频讲解：https://www.bilibili.com/video/BV1Te411N7SX
题解链接：https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
看了下感觉确实不难，最开始我还在想加一句：if(dp[j-1]==dp[j-2])判断下
前一个是否已经被打劫了，但是实际上，无论前一个是否被打劫了 dp[j] = max(dp[j- 2] + nums[j-1], dp[j - 1]);都成立的。具体大家可以自己分情况思考。

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size()+1,0);dp[1] = nums[0];for(int j=2;j<=nums.size();j++){dp[j] = max(dp[j- 2] + nums[j-1], dp[j - 1]);//}return dp[nums.size()];}
};

213. 打家劫舍 II

视频讲解：https://www.bilibili.com/video/BV1oM411B7xq
题解链接：https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
代码随想录给出了三种可能，实际上只有两种可能，因为很简单，既然首位相连，所以相当于第一家和最后一家，只能抢劫一家。至于所谓的只考虑中间的，太傻了，多了两个机会肯定比只考虑中间的抢的钱更多。
情况：考虑包含尾元素，不包含首元素

考虑包含首元素，不包含尾元素

class Solution {
public:int rob1(vector<int>& nums,int start){vector<int> dp(nums.size()+1,0); dp[start+1] = nums[start];for(int j=start+2;j<=nums.size();j++){dp[j] = max(dp[j- 2] + nums[j-1], dp[j - 1]);//}return start ? dp[nums.size()] : dp[nums.size()-1];}int rob(vector<int>& nums) {if(nums.size()==0)return 0;if(nums.size()==1)return nums[0];return max(rob1(nums,0),rob1(nums,1));       }};

还在想怎么变化位置范围，实际上不用变化，直接照着dp[]开始。大不了多占一个单元。没必要把代码搞玛法，只为了节省一个数组单元。

分析到这里，本题其实比较简单了。 剩下的和198.打家劫舍 (opens new window)就是一样的了。

337. 打家劫舍 III

视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY
题解链接：https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
玛德，树形结构确实够难，忘掉了

class Solution {
public:int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left，相当于不考虑左孩子了if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right，相当于不考虑右孩子了// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子return max(val1, val2);}
};

很简单的递归算法，不断递归迭代。首先只要父节点没偷，左右子树可以偷的，如果叶子节点就偷，不要担心叶子节点能不能偷，只要是按照算法走，叶子节点肯定能偷，不能偷的都跳过去了。然后判断下偷父节点值还是偷左右叶子节点值。这样层层递归，虽然有点绕，但是整体不难。

class Solution {
public:unordered_map<TreeNode* , int> umap; // 记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};

卧槽，太妙了，确实，用一个map记录下每个节点的值，这样方便太多了，不用重复递归计算了。
第三种方法，树形的动态规划：
我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
确定终止条件：在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回if (cur == NULL) return vector{0, 0};
千言不如一图，把下面的图，看懂即可。从下往上

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组，0：不偷，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);// 偷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};}
};

还是不算难，有点绕脑子。