代码随想录算法训练营第四十七天| ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

打家劫舍 

题目链接：198. 打家劫舍 - 力扣（LeetCode）

思路：每一家的最大收益来源只有两个，一个是这家不偷，那么最大收益等于从上一家出来的最大收益，另一个是偷这一个家，因此最大收益等于从上上一家出来的最大收益加这一家的收益。

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

打家劫舍II  

题目链接：213. 打家劫舍 II - 力扣（LeetCode）

思路：本题和上一题的区别在于本题数组是环形数组，似乎无从下手。这里参考官网写法

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums.size()==1)return nums[0];
        int result1=R(nums,0,nums.size()-2);
        int result2=R(nums,1,nums.size()-1);
        return max(result1,result2);
    }
    int R(vector<int>& nums,int start,int end){
        if(start==end)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-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
};

打家劫舍III

题目链接：337. 打家劫舍 III - 力扣（LeetCode）

思路：这一题让我想到了放摄像头那一题，总之不会。

递归法，也是我一开始想到的做法：

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->left
        if (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);
    }
};

动态规划法：

对于树形dp，dp数组的长度是2，因为我们有递归的过程，每个dp数组只需存储偷或不偷的最大收益。

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};
    }
};