代码随想录算法训练营第四十八天 | 198.打家劫舍 & 213. 打家劫舍 II & 337. 打家劫舍 III

1. 打家劫舍

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

dp[i] 偷前 i 家的最大收益

class Solution {
    public int rob(int[] nums) {
        // dp[i] 偷前i家
        int length = nums.length;
        int[] dp = new int[length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= length; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        return dp[length];
    }
}

2. 打家劫舍 II

213. 打家劫舍 II - 力扣（LeetCode）

考虑首尾只偷一家的情况

class Solution {
    public int rob(int[] nums) {   
        int length = nums.length;
        if(length == 1)
            return nums[0];
        return Math.max(robMax(nums, 0, length-1), robMax(nums, 1, length)); 
        // 首尾只考虑其中一个
    }
    //[)
    public int robMax(int[] nums, int start, int end){
        // dp[i] 偷下标为前i家
        int[] dp = new int[nums.length-1]; // 少考虑一家 -1
        dp[0] = nums[start];
        if(dp.length == 1) return dp[0]; //只有一家
        dp[1] = Math.max(nums[start],nums[start + 1]);
        if(dp.length == 2) return dp[1]; //只有两家
 
        for(int i = 2; i < dp.length; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i+start]); //注意nums的起点
        }
        return dp[dp.length-1];
    }
}

3. 打家劫舍 III 

337. 打家劫舍 III - 力扣（LeetCode）

一个节点偷不偷，却决于它的孩子节点偷不偷

后序遍历，获得孩子节点偷不偷的价值，再判断当前节点偷不偷

class Solution {
    public int rob(TreeNode root) {
        int[] res = robChild(root);
        return Math.max(res[0], res[1]);
    }
    
    public int[] robChild(TreeNode root){
        // res[0] 不偷 res[1] 偷
        int[] res = new int[2];
        if(root == null) return res;
 
        int[] left = robChild(root.left);
        int[] right = robChild(root.right);
 
        // 当前节点不偷，就可以偷孩子，偷孩子分偷不偷
        // Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
        res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
 
        // 当前节点偷，就不可以偷孩子
        // 当前节点偷 + 左孩子不偷 + 右孩子不偷
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}