代码随想录算法训练营 | 198.打家劫舍，213.打家劫舍II，337.打家劫舍III

198.打家劫舍
题目链接：198.打家劫舍
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍
日期：2024-10-13

想法：dp[i]到第i个房子时能偷的最多的钱；递推公式：是上上一栋房子的dp[i - 2]加上这栋房子的钱nums[i]大还是上一家邻居偷的钱dp[i - 1]的大；初始化因为有i - 2；所以初始化dp[0]和dp[1]；顺序，从前往后；打印。
Java代码如下：

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        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];
    }
}

213.打家劫舍II
题目链接：213.打家劫舍II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍II
日期：2024-10-13

想法：因为首尾相连，所以nums得分两种情况，要头不要尾和要尾不要头，rob1(nums, 0, nums.length - 2)和rob1(nums, 1, nums.length - 1)这两种，注意start = end的时候要返回nums[start]
Java代码如下：

class Solution {
    public int rob1(int[] nums, int start, int end) {
        if(start == end) return nums[start];
        int[] dp = new int[nums.length];
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }

    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int res1 = rob1(nums, 0, nums.length - 2);
        int res2 = rob1(nums, 1, nums.length - 1);
        return Math.max(res1, res2);
    }
}

337.打家劫舍III
题目链接：337.打家劫舍III
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍III
日期：2024-10-13

想法：dp[0]表示不抢当前节点的最大钱，dp[1]为抢，后序遍历。
Java代码如下：

class Solution {
    public int rob(TreeNode root) {
        int[] dp = rob1(root);
        return Math.max(dp[0], dp[1]);
    }
    public int[] rob1(TreeNode root) {
        int[] dp = new int[2];
        if(root == null) return dp;
        int[] left = rob1(root.left);
        int[] right = rob1(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;
    }
}