代码随想录第四十八天 | 198.打家劫舍， 213.打家劫舍II，337.打家劫舍III

198.打家劫舍

看完想法：这里的偷/不偷，和背包问题中的放/不放感觉是一个道理，所以在dp递推公式中仍旧使用max(dp[i-2] + nums[i], dp[i-1])

int rob(vector& nums) {
    vector dp(nums.size()+1,0);
    if(nums.size()==0) return 0;
    if(nums.size()==1) return nums[0];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    //0和1的情况要单独用if列出，所以这里起始点是i=2
    for(int i = 2; iright);
        // 偷cur，那么就不能偷左右节点,所以是left[0] + right[0]
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取left/right中偷不偷较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
    int rob(TreeNode* root) {
        vector result = robTree(root);
        return max(result[0], result[1]);
    }