打家劫舍

打家劫舍I II III

198.打家劫舍 I

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        //有相应的测试样例才需要，没有不用也行
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(n);

        //base case
        dp[0]=nums[0];
        dp[1]=max(nums[0], nums[1]);

        for(int i=2;i<n;i++){
            //对于每家可以选择偷或者不偷
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};

213.打家劫舍 II

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        
        if(n==0) return 0;
        if(n==1) return nums[0];

        return max(helper(nums, 0, n-2), helper(nums, 1, n-1));
    }
    int helper(vector<int>& nums, int start, int end){
        int n=nums.size();

        //dp[i]表示长度为i的数组，最多能偷取多少钱
        vector<int> dp(n);

        //base case
        if(start==0){
            dp[0]=nums[0];
            dp[1]=max(nums[0], nums[1]);
        }
        if(start==1){
            dp[0]=0;
            dp[1]=nums[1];
        }

        for(int i=2;i<=end;i++){
            //对于每家可以选择偷或者不偷
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
};

337.打家劫舍 III

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res = helper(root);
        return max(res[0], res[1]);
    }

    // 长度为2的数组，0：不偷，1：偷
    vector<int> helper(TreeNode* root) {
        if (root == nullptr){
            return {0, 0};
        }

        vector<int> left = helper(root->left);
        vector<int> right = helper(root->right);

        // 偷当前节点，字节点不偷
        int res1 = root->val + left[0] + right[0];

        // 不偷当前节点，字节点可偷可不偷，取决于收益大小
        int res2 = max(left[0], left[1]) + max(right[0], right[1]);

        return {res2, res1};  //注意顺序，res2在前，res1在后，因为是后序遍历
    }
};