【c++刷题笔记-动态规划】day40： 198.打家劫舍 、 213.打家劫舍II 、 337.打家劫舍III

198. 打家劫舍 - 力扣（LeetCode）

思路：两种状态，在偷和不偷之间判断最大的值，然后递推

重点： dp[i]=max(dp[i-1],dp[i-2]+nums[i]);

class Solution {
public:
    int rob(vector& nums) {
        int n=nums.size();
        vectordp(n);
        if(n==1){
            return nums[0];
        }
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);//取最大的
        for(int i=2;iright);
        //偷cur，那么就不能偷左右节点。
        int val1=root->val+left[0]+right[0];
        //不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2=max(left[0],left[1])+max(right[0],right[1]);
        return {val2,val1};
    }
};

总结

打家劫舍问题有俩个状态，偷和不偷。依赖前两个状态。遇到循环问题分为两种情况讨论，[0,n-2],[1,n-1]。树形dp使用长度为2的数组，下标0表示不偷，下标1表示偷。利用这两个状态进行推导