代码随想录算法训练营第三十九天

LeetCode.198 打家劫舍

题目链接 打家劫舍

题解

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

解题思路

这是一个用动态规划解决 “打家劫舍” 问题的代码。

问题背景是：有沿街的房屋，每间房有一定现金，相邻房屋不能同时偷窃（否则报警），要计算不触发警报时能偷到的最高金额。

代码的思路如下：

首先处理边界情况，如果只有一间房屋，那么能偷到的最高金额就是这间房屋的现金数，直接返回即可。

然后定义一个动态规划数组 dp，其中 dp [i] 表示偷窃前 i+1 间房屋（也就是从下标 0 到 i 的房屋）能得到的最高金额。

接着初始化数组的前两个元素：dp [0] 就是第一间房屋的现金数，因为只有这一间房；dp [1] 则是前两间房屋中现金较多的那间的金额，因为不能同时偷相邻的，所以选大的那个。

之后从第三间房屋（下标 2）开始循环计算：对于第 i 间房屋，有两种选择，要么偷这间，那么就不能偷第 i-1 间，此时能得到的金额是偷前 i-2 间的最高金额加上第 i 间的现金；要么不偷这间，那么能得到的金额就是偷前 i-1 间的最高金额。这两种情况取最大值，就是 dp [i] 的值。

最后，数组的最后一个元素 dp [nums.length-1] 就是偷窃所有房屋能得到的最高金额，将其返回。

这个解法的时间复杂度是 O (n)，因为只需要遍历一次房屋数组；空间复杂度是 O (n)，因为使用了一个长度为 n 的 dp 数组（不过可以优化到 O (1)，只需要用两个变量来存储前两个状态即可）。

LeetCode.213 打家劫舍Ⅱ

题目链接 打家劫舍Ⅱ

题解

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        int[] tmpNums = new int[len];
        for(int i = 0;i<len - 1;i++){
            tmpNums[i] = nums[i];
        }    
        int value1 = rob1(tmpNums);
        for(int i = 1;i<len;i++){
            tmpNums[i-1] = nums[i];
        }
        int value2 = rob1(tmpNums);
        return Math.max(value1,value2);
    }
    public int rob1(int[] nums) {
        if(nums.length == 1) return nums[0];
        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-2] + nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

解题思路

这是解决「打家劫舍 II」问题的代码，在原问题基础上增加了一个约束：房屋围成一圈（即第一间和最后一间也视为相邻，不能同时偷窃）。

代码的核心思路是将环形问题转化为两个线性问题：

1. 不考虑最后一间房，只计算从第一间到倒数第二间的最高金额（value1）
2. 不考虑第一间房，只计算从第二间到最后一间的最高金额（value2）
3. 最终结果取这两个值中的较大者

具体实现步骤：

• 先处理边界情况：如果只有一间房，直接返回该房屋的金额
• 构造第一个临时数组 tmpNums，包含除最后一间外的所有房屋
• 调用 rob1 方法计算这个临时数组的最高金额（value1）
• 重新构造临时数组 tmpNums，包含除第一间外的所有房屋
• 再次调用 rob1 方法计算这个临时数组的最高金额（value2）
• 返回 value1 和 value2 中的最大值

其中 rob1 方法就是解决「打家劫舍 I」的动态规划函数：

• 用 dp [i] 表示前 i+1 间房屋能偷到的最高金额
• 状态转移方程为：dp [i] = max (dp [i-2] + nums [i], dp [i-1])
• 即对于第 i 间房，要么偷（加上前 i-2 间的最高金额），要么不偷（取前 i-1 间的最高金额）

通过这种拆分方式，成功将环形约束转化为两个线性问题，从而复用了原问题的解法。

LeetCode.337 打家劫舍III

题目链接 打家劫舍III

题解

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

解题思路

这是解决「打家劫舍 III」问题的代码，该问题将房屋排列成二叉树结构，约束条件为：不能偷窃相连的节点（父节点和子节点视为相邻，不能同时偷窃），需要计算能偷到的最高金额。

代码采用了深度优先搜索（DFS）结合动态规划的思路，核心是对每个节点考虑两种状态：

1. 定义返回数组 res，其中：

   • res [0] 表示不偷当前节点时，以该节点为根的子树能偷到的最高金额
   • res [1] 表示偷当前节点时，以该节点为根的子树能偷到的最高金额

2. 递归处理逻辑：

   • 若当前节点为空，返回两个元素都为 0 的数组
   • 递归计算左子树和右子树的结果（left 和 right 数组）
   • 不偷当前节点时（res [0]）：可以偷或不偷左右子节点，取左右子树两种状态的最大值之和
   • 偷当前节点时（res [1]）：不能偷左右子节点，金额为当前节点值加上左右子树不偷时的金额之和

3. 最终结果：根节点两种状态的最大值，即 max (res [0], res [1])

这种解法通过后序遍历方式，从叶子节点向根节点计算，每个节点只需要处理一次，时间复杂度为 O (n)（n 为节点数量），空间复杂度为 O (h)（h 为树的高度，递归栈空间）。