代码随想录训练营day48, 打家劫舍系列问题

打家劫舍

可以体会一下, 当前房屋偷不偷取决于前一个房屋和前两个房屋是否被偷了, 所以这种依赖关系就是dp的递推公式

1. dp[i]: 考虑下标i以内的房屋, 最多可以偷窃的金额为dp[i]
2. 递推公式: 决定的因素就是第i房间是偷还是不偷, 然后比较max
   1. 偷i的话, 那么dp[i] = dp[i-2] + nums[i] (不会偷上一个, 然后加上i)
   2. 不偷i的话, 那么dp[i] = dp[i - 1]
3. 初始化: 可以从递推公式看出, 基础就是dp[0]和dp[1], 从定义可以看出dp[0]一定是nums[0], dp[1]一定是nums[0]和nums[1]的最大值(0-最多偷窃的金额为nums[0]; 1-只有两间房, 偷金额大的那个)
4. 遍历顺序: 从前到后
5. 最后dp数组的最后一个值就是结果, 所以其实是length-1的位置

class Solution {
    public int rob(int[] nums) {
        //前面要多剪剪枝
        if(nums.length == 0 || nums == null){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        //开始dp数组创建和初始化
        int[] dp = new int[nums.length + 1];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        //开始从前向后遍历
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        //找的是最后位置, 所以减一
        return dp[nums.length - 1];
    }
}

打家劫舍II

唯一的区别就是变成环了

成环主要考虑三种情况:

1. 考虑不包含首尾元素
2. 考虑包含首元素, 不包含尾元素
3. 考虑包含尾元素, 不包含首元素

(而其实情况二和三已经包含了情况一, 所以比较二三就行了)

可以先看一下完整版代码: 注意关于start和end的变量设置

class Solution {
    public int rob(int[] nums) {
        //还是一样的剪枝
        int len = nums.length;
        if(nums == null || len == 0){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        //开始判断两种条件
        //首先是只考虑头
        int result1 = robRange(nums, 0, len - 2);
        //然后是只考虑尾
        int result2 = robRange(nums, 1, len - 1);
        return Math.max(result1, result2);
    }
 
    public int robRange(int[] nums, int start, int end){
        //这里还要判断一下, 两个数相等, 就去第一个, 否则后面的max会出错
        if(end == start) return nums[start];
        //这里还是打家劫舍逻辑
        int[] dp = new int[nums.length + 1];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for(int i = start + 2; i <=end; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
}

简化版: 动态方程就是1. 偷了n(dp[n + 1]就是dp[n]) 2. 没偷n(dp[n + 1]就是dp[n-1] + num)

这里的思想就是用n+1的位置

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0 || nums == null){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        int result1 = robHelper(nums, 0, len - 1);
        int result2 = robHelper(nums, 1, len);
        return Math.max(result1, result2);
 
    }
    public int robHelper(int[] nums, int start, int end){
        if(start == end) return nums[start];
        int pre = 0, cur = 0, temp = 0;
        //利用滚动数组来模拟dp
        for(int i = start; i < end; i++){
            temp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = temp;
        }
        return cur;
 
    }
}

打家劫舍III

这次就变成了二叉树

回想起之前的遍历方式, 这里是后序, 因为通过递归函数的返回值来做下一步计算

若抢了当前节点, 两个孩子就不能动, 如果没抢当前节点, 就可以考虑抢左右孩子

树形dp, 结合递归三部曲和动规五部曲

1. 确定返回值: 就是返回dp数组, 长度为2.下标为0记录不偷该节点所得到的最大金钱, 下标为1记录偷该节点所得到的最大金钱

2. 确定终止条件: 如果遇到空节点时, 偷或不偷都是0, 所以return

3. 遍历顺序: 使用后序

4. 单层递归的逻辑:

   1. 如果偷当前, 两个孩子就不能偷, cur.val + left[0] + right [0]
   2. 如果不偷, 就可以偷孩子 max(left[0], left[1]) + max(right[0], right[1])

   最终就是return(val2, val1), 不偷得到的最大钱和偷得到的

class Solution {
    public int rob(TreeNode root) {
        int[] res = robRecur(root);
        return Math.max(res[0], res[1]);
    }
 
    private int[] robRecur(TreeNode root){
        //穿件一个长度为2的数组
        int[] dp =  new int[2];
        //先确定终止条件
        if(root == null){
            return dp;
        }
 
        //后序遍历
        int[] left = robRecur(root.left);
        int[] right = robRecur(root.right);
        //单层逻辑
        //首先是不偷的情况, 那么就是偷孩子, 
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //然后是偷的情况, 所以孩子就不能偷
        dp[1] = root.val + left[0] + right[0];
        return dp;
    }
}