代码随想录算法训练营day48 | LeetCode 198. 打家劫舍 213. 打家劫舍 II 337. 打家劫舍 III

198. 打家劫舍（题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台）

思路：dp题除背包外的另外一类题目，重点不在于看前面的情况，而在于考虑本节点的情况。一种情况，选择本节点；另一种情况，不选择本节点，看哪种情况下的值最大。初始化也有所不同，不是简单地dp[0]=0,dp[1]=1诸如此类，dp[1]要考虑dp[0]的大小才能决定。

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

213. 打家劫舍 II（题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台）

思路：环形数组，第一次见dp中这样的设置，其实很简单，总体上考虑两种情况：情况一：考虑除数组头外的其他所有元素；情况二：考虑除数组尾外的其他所有元素。最后取这两个里面的最大值就好。

int robRange(vector<int>& nums, int start, int end){if(end==start) return nums[end];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];
}int rob(vector<int>& nums) {int size = nums.size();if(size==1) return nums[0];int result1 = robRange(nums, 0, size-2);int result2 = robRange(nums, 1, size-1);return max(result1, result2);
}

337. 打家劫舍 III（题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台）

思路：树形dp，dp的做法和二叉树的遍历的做法没有很大差异，或者说dp的做法就是基于二叉树的遍历做了一点点的改进，只是为了让它更像是动态规划。

递归遍历做法：

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];int val1 = root->val;if(root->left) val1 += rob(root->left->left)+rob(root->left->right);if(root->right) val1 += rob(root->right->left)+rob(root->right->right);int val2=rob(root->left)+rob(root->right);umap[root] = max(val1, val2);return max(val1, val2);
}

其中用umap是为了让树中每个节点只遍历一遍，避免反复求值。

dp做法：

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