代码随想录day39 动态规划7

198.打家劫舍

思路：第i个房子偷与不偷，取决于第i-2个房子和第i-1个房子

注意：注意下标的一致性。现在的下标含义是房子的下标，而不是第几个房子。（也可以更改）

五部：

1.dp[i]:在第i个房子时，最多的钱

2.dp[i]=max(dp[i-2]+nums[i],dp[i-1]);

3.由递推式，知道要初始化dp0和dp1

4.从前到后遍历。

代码：

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

        vector<int>dp(n,0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);

        for(int i=2;i<n;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
};

213.打家劫舍II

思路：在上题基础上，增加了环形。所以分成三种情况：

1.不含首尾元素；

2.可能包含首元素不含尾元素

3.可能包含尾元素不含首元素

利用198的函数即可

注意：其中，情况2 和情况3 都包含了情况1，所以情况1在计算中可以忽略

代码：

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

337.打家劫舍III    --树形dp

思路：就是从树根节点出发，决定每个节点是偷还是不偷。结合了树的遍历和动规。因为需要左右 的值来决定中间的值，所以选择后序遍历。

注意：

树的分析：

1.参数，返回值：应该return一个两个元素的数组，分别代表偷当前节点和不偷当前节点的值。参数为树节点

2.终止条件：遇到空节点return（0，0），遇到叶子返回（叶子val，0）

3.遍历顺序：后序遍历，因为需要左右的值。且需要记录左右的值

vector<int>left=rob(root->left) 

4.单层逻辑：val1=cur->val+left(1)+right(1)：偷该节点

val2=max(left[0],left[1])+max(right[0].right[1]);不偷该节点（可以选择左右孩子偷还是不偷，选最大 的）

最后return（val1，val2）

代码：

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int>res=robTree(root);
        return max(res[0],res[1]);
    }
    vector<int>robTree(TreeNode*cur){
        if(cur==nullptr)return {0,0};//(偷该节点，不偷该节点)
        if(cur->left==nullptr&&cur->right==nullptr)return{cur->val,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};
    }
};