代码随想录算法训练营第三十八天-198打家劫舍、213打家劫舍II、337打家劫舍III

前言
状态：都是看了解析写出。
更新

1	24-06-26 初始记录

初步题解

198 打家劫舍

题目链接：(https://leetcode.cn/problems/house-robber)

确定 dp[i] 的含义：下标 i 及之前的房间能偷的最大金币数。
递推公式：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。（分为两种情况，偷/不偷）
dp 数组的初始化：dp[0] = num[0], dp[1] = Math.max(num[0], num[1])。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

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

213 打家劫舍 II

题目链接：(https://leetcode.cn/problems/house-robber-ii)

本题的递推与上一题相同。区别在于要不要统计头尾。思路是去除尾和去除头分别求一次最大值。然后选较大的那个。

public class LE213 {  
    public static void main(String[] args) {  
        int rob = rob(new int[]{200, 3, 140, 20, 10});  
        System.out.println(rob);  
    }  
  
    public static int rob(int[] nums) {  
        if (nums.length == 1) {  
            return nums[0];  
        }  
        return Math.max(rob1(nums, 0, nums.length - 1), rob1(nums, 1, nums.length));  
    }  
      
    public static int rob(int[] nums, int start, int end) {  
        int[] dp = new int[end - start];  
  
        dp[0] = nums[start];  
        if (dp.length == 1) {  
            return dp[0];  
        }  
        dp[1] = Math.max(nums[start], nums[start + 1]);  
  
        for (int i = 2; i < dp.length; i++) {  
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + 2]);  
            start++;  
        }  
  
        System.out.println(Arrays.toString(dp));  
  
        return dp[dp.length - 1];  
    }  
  
    /**  
     * 方法二：直接交换  
     */  
    public static int rob1(int[] nums, int start, int end) {  
        // x为上上层的最大值，y为上一层的最大值。  
        int x = 0, y = 0;  
        for (int i = start; i < end; i++) {  
            int temp = Math.max(x + nums[i], y);  
            x = y;  
            y = temp;  
        }  
  
        return y;  
    }  
}

337 打家劫舍 III

题目链接：(https://leetcode.cn/problems/house-robber-iii)

动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为 2 的数组，记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形 dp 的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

递归三部曲：

确定递归函数的参数和返回值。求一个节点两个状态的金钱值，返回值就是一个长度为 2 的数组。本题 dp 数组就是一个长度为 2 的数组
确定终止条件。遇到空节点返回。
确定遍历顺序。后序遍历。

动规五部曲：

确定 dp[i] 的含义：下标 0 表示不偷的最大，下标 1 表示偷的最大。
递推公式即单层递归的逻辑：dp[0] = cur->val + left[0] + right[0]，dp[1] = max(left[0], left[1]) + max(right[0], right[1])。（分为两种情况，偷/不偷：偷当前节点 dp[1]，值为当前节点值 + 不偷左右的节点的值；不偷当前节点 dp[0]，值为左孩子偷/不偷的最大值 + 右孩子偷/不偷的最大值）
dp 数组的初始化：dp[0] = 0, dp[1] = 0，这里的初始化与递归的终止条件相。
遍历顺序：后序遍历。
打印 dp 数组（用于 debug）

public int rob(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
    int[] dp = robDFS(root);  
    return Math.max(dp[0], dp[1]);  
}  
  
private int[] robDFS(TreeNode root) {  
    if (root == null) {  
        return new int[2];  
    }  
  
    int[] left = robDFS(root.left);  
    int[] right = robDFS(root.right);  
  
    return new int[]{Math.max(left[0], left[1]) + Math.max(right[0], right[1]), root.val + left[0] + right[0]};  
}

看解析