【代码随想录】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]);
    }
};