(47/60)打家劫舍、打家劫舍Ⅱ、打家劫舍Ⅲ

day47

打家劫舍

leetcode：198. 打家劫舍

动态规划

代码实现

/*
偷到下标为i的最大金额数为dp[i]
偷i、不偷i：dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);
正序遍历
*/

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

打家劫舍Ⅱ

leetcode：

动态规划

思路

拆分成两个打家劫舍Ⅰ：考虑头元素、考虑尾元素。

代码实现

/*
偷到下标为i的最大金额数为dp[i]
偷i、不偷i：dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);
正序遍历
*/

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]);
        int result1 = robRange(nums,0,nums.size()-2);
        int result2 = robRange(nums,1,nums.size()-1);
        cout<< result1<<" "<<result2;
        return max(result1,result2);
    }

    int robRange(vector<int>& nums,int begin,int end){
        vector<int> dp(nums.size(),0);
        dp[begin] = nums[begin];
        dp[begin + 1] = max(nums[begin],nums[begin + 1]);
        for(int i = begin + 2;i <= end;i++){
            dp[i] = max(dp[i-2] + nums[i],dp[i-1]);
        }
        return dp[end];
    }
};

打家劫舍Ⅲ

leetcode：337. 打家劫舍 III

动态规划

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> robTree(TreeNode* cur){
        if(!cur) return vector<int>{0,0};
        vector<int> leftdp = robTree(cur->left);
        vector<int> rightdp = robTree(cur->right);
        // dp[0]不偷;dp[1]偷
        int val1 = cur->val + leftdp[0] + rightdp[0];   // 偷
        int val2 = max(leftdp[0],leftdp[1]) + max(rightdp[0],rightdp[1]);   // 不偷

        return vector<int>{val2,val1};
    }

    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0],result[1]);
    }
};