LeetCode打家劫舍II(House Robber II) DP代码输出错误排查

• 已正确实现House Robber（打家劫舍）的求解代码，代码可正常运行：

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

• 尝试基于上述代码改造求解House Robber II（打家劫舍II），核心思路为：由于房屋首尾相邻，无法同时盗取第一栋和最后一栋房屋，因此将可盗取范围拆分为两个独立区间，分别计算两个区间的最大盗取金额后取最大值作为结果：
  • 区间1：第一栋到倒数第二栋房屋
  • 区间2：第二栋到最后一栋房屋
• 改造后的代码无法返回正确结果，问题代码如下：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0], nums[1]);
        return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
    public int solve(int[] nums, int start, int end){
        int[] dp = new int[end + 2];
        for(int i = end - 1; i >= start; i--){
            dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
        }
        return dp[start];
    }
}

你的区间拆分思路完全正确，问题出在solve方法的遍历边界写错了：

• 原正确实现的倒序动态规划逻辑，要求从区间的最后一个房屋索引开始往前遍历，才能覆盖区间内所有房屋的选/不选判断
• 你写的solve方法中，循环起始值设为了end - 1，直接跳过了每个传入区间的最后一个房屋：
  • 计算[0, n-2]区间时，漏掉了索引为n-2的倒数第二栋房屋
  • 计算[1, n-1]区间时，漏掉了索引为n-1的最后一栋房屋
    相当于两个计算区间都少统计了边界处的一栋房屋，最终返回结果自然错误。

只需要修改solve方法的循环起始值，从end位置开始倒序遍历，覆盖区间内所有房屋即可，修正后的完整代码如下：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0], nums[1]);
        return Math.max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }
    public int solve(int[] nums, int start, int end){
        int[] dp = new int[end + 2];
        // 修正遍历起点，从区间最后一个房屋开始倒推
        for(int i = end; i >= start; i--){
            dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
        }
        return dp[start];
    }
}

内容的提问来源于stack exchange，提问作者Jessie