小学生都能看懂的题解 | #打家劫舍(二)#

打家劫舍(二)

https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815

问题描述

你是一个小偷，准备去偷一排房间里的钱。每个房间里都有一些现金，但是有一个特别的地方：这些房间是围成一个圈的。也就是说，第一个房间和最后一个房间是相邻的。你不能同时偷相邻的房间。

我们的目标是找到一个偷钱的计划，让你偷到的钱最多。

解决方案的思路

分情况讨论：
- 由于房间是环形的，我们可以把问题分成两种情况来考虑：
  - 不偷第一个房间：这样只考虑从第二个房间到最后一个房间的情况。
  - 不偷最后一个房间：这样只考虑从第一个房间到倒数第二个房间的情况。
- 这两个情况可以通过分别计算得到，最后取最大的结果。
使用动态规划：
- 对于每个情况，我们用动态规划的方法来计算。
- 动态规划的意思就是：我们把大问题分成小问题来解决，并把小问题的答案存起来，方便后续使用。
状态转移：
- 设 dp[i] 表示偷到第 i 间房子时的最大金额。
- 每间房子有两个选择：
  - 不偷这间房子，最多的钱就是前一间房子能偷到的钱。
  - 偷这间房子，那么我们就不能偷相邻的房子，最多的钱就是这间房子的钱加上前两间房子能偷到的钱。
- 公式就是： [ dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) ]

Java代码解释

下面是实现这个方案的Java代码，我们会逐行解释每一部分：

public class HouseRobberII {
    public int rob(int[] nums) {
        int n = nums.length;

        // 如果只有一个房间，直接返回这个房间的钱
        if (n == 1) {
            return nums[0];
        }
        
        // 分别计算两种情况
        // 1. 不偷第一个房间，考虑房间 1 到 n-1
        int max1 = robLinear(nums, 1, n - 1);
        
        // 2. 不偷最后一个房间，考虑房间 0 到 n-2
        int max2 = robLinear(nums, 0, n - 2);
        
        // 返回两种情况中的最大值
        return Math.max(max1, max2);
    }
    
    // 线性房屋偷窃函数
    private int robLinear(int[] nums, int start, int end) {
        int prev1 = 0; // 代表 dp[i-2]
        int prev2 = 0; // 代表 dp[i-1]
        
        for (int i = start; i <= end; i++) {
            // 当前的最多钱是前两个选择的最大值
            int current = Math.max(prev2, nums[i] + prev1);
            // 更新前两个状态
            prev1 = prev2; // 更新为 dp[i-2]
            prev2 = current; // 更新为 dp[i-1]
        }
        
        return prev2; // 返回 dp[n-1]
    }
    
    public static void main(String[] args) {
        HouseRobberII robber = new HouseRobberII();
        System.out.println(robber.rob(new int[]{1, 2, 3, 4})); // 输出6
        System.out.println(robber.rob(new int[]{1, 3, 6})); // 输出6
        System.out.println(robber.rob(new int[]{2, 10, 5})); // 输出10
        System.out.println(robber.rob(new int[]{5, 1, 2, 10, 6})); // 输出16
    }
}

代码逐行解释

类定义：我们创建了一个名叫 HouseRobberII 的类，这里面有一个方法 rob，用来计算最多能偷到的钱。
处理特殊情况：
- int n = nums.length;：获取房间的数量。
- if (n == 1)：如果只有一个房间，直接返回这个房间里的钱，因为没有其他选择。
分别计算两种情况：
- int max1 = robLinear(nums, 1, n - 1);：不偷第一个房间，计算从第二个房间到最后一个房间的最大金额。
- int max2 = robLinear(nums, 0, n - 2);：不偷最后一个房间，计算从第一个房间到倒数第二个房间的最大金额。
返回最大值：return Math.max(max1, max2);：返回两种情况中能偷到的最多的钱。
线性偷窃函数：
- private int robLinear(int[] nums, int start, int end)：这个方法用来处理线性房子的问题，只需要给定开始和结束的索引。
- 在这个方法中，使用 prev1 和 prev2 来保存前两个状态的最大值。
循环计算：
- for (int i = start; i <= end; i++)：从 start 到 end 遍历每个房间。
- int current = Math.max(prev2, nums[i] + prev1);：计算当前能偷到的最多钱。
- 更新 prev1 和 prev2 的值，为下一个房间准备。
返回结果：最后返回 prev2，它保存的是最多的金额。
主函数：
- 在 main 方法中，我们测试了几个例子，打印出能偷到的最大金额。