代码训练营第50天：leetcode198打家劫舍｜leetcode213打家劫舍2｜leetcode337打家劫舍3

leetcode198：打家劫舍

文章讲解：leetcode198

leetcode213：打家劫舍2

文章讲解：leetcode213

leetcode337：打家劫舍3

文章讲解：leetcode337

目录

1，leetcode198 打家劫舍

2，leetcode213 打家劫舍2

3，leetcode337 打家劫舍3

---

1，leetcode198 打家劫舍

这道题就是直接的递归思路做。dp数组含义就是偷到第i家时能偷到的最多的钱。无非就两种情况，如果不偷第i家，那dp[i]=dp[i-1]，如果偷第i家，那么第i-1家不可能偷，dp[i]=nums[i]+dp[i-2];

max一下就行。

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

2，leetcode213 打家劫舍2

这道题的区别就在于递推的时候首位相连了，就意味着首尾只能选一个，那其实dp的时候做两次，一次包含首，一次包含尾，取最大即可

class Solution {
public:
    int robdp(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        if(nums.size()==2)return max(nums[0],nums[1]);
        vector<int>dp(nums.size()+1,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2;isize();i++){
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
    int rob(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        if(nums.size()==2)return max(nums[0],nums[1]);
        vector<int> left(nums.begin(),nums.end()-1);
        vector<int> right(nums.begin()+1,nums.end());
        int max1 = robdp(left);
        int max2 = robdp(right);
        return max(max1,max2);
    }
};

3，leetcode337 打家劫舍3

这道题实际上就是把上面的-1变成子树，-2变成子树的子树。但是具体的遍历还真没有思路。

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

猪脑烧了，受不了了。