【代码随想录】day48

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

一、198打家劫舍

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

二、213打家劫舍II

class Solution {
public:int helper(vector<int>& nums, int start, int end) {vector<int> dp(2, 0);for (int i = start; i < end; i ++) {dp.push_back(max(dp.back(), dp[dp.size()-2] + nums[i]));}return dp.back();}int rob(vector<int>& nums) {if (nums.size() == 1) {return nums.back();}int res1 = helper(nums, 0, nums.size() - 1);int res2 = helper(nums, 1, nums.size());return max(res1, res2);}
};

三、337打家劫舍III

class Solution {
public:unordered_map<TreeNode*, int> umap;int rob(TreeNode* root) {if (root == nullptr) {return 0;}if (root->left == nullptr && root->right == nullptr) {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);        }
};

优化版：

class Solution {
public:vector<int> robTree(TreeNode* cur) {if (cur == nullptr) {return vector<int>(2, 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};}int rob(TreeNode* root) {vector<int> dp = robTree(root);return max(dp[0], dp[1]);}
};