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

问题描述

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

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

解决方案的思路

1. 分情况讨论：

   • 由于房间是环形的，我们可以把问题分成两种情况来考虑：
     • 不偷第一个房间：这样只考虑从第二个房间到最后一个房间的情况。
     • 不偷最后一个房间：这样只考虑从第一个房间到倒数第二个房间的情况。
   • 这两个情况可以通过分别计算得到，最后取最大的结果。

2. 使用动态规划：

   • 对于每个情况，我们用动态规划的方法来计算。
   • 动态规划的意思就是：我们把大问题分成小问题来解决，并把小问题的答案存起来，方便后续使用。

3. 状态转移：

   • 设 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
    }
}

代码逐行解释

1. 类定义：我们创建了一个名叫 HouseRobberII 的类，这里面有一个方法 rob，用来计算最多能偷到的钱。

2. 处理特殊情况：

   • int n = nums.length;：获取房间的数量。
   • if (n == 1)：如果只有一个房间，直接返回这个房间里的钱，因为没有其他选择。

3. 分别计算两种情况：

   • int max1 = robLinear(nums, 1, n - 1);：不偷第一个房间，计算从第二个房间到最后一个房间的最大金额。
   • int max2 = robLinear(nums, 0, n - 2);：不偷最后一个房间，计算从第一个房间到倒数第二个房间的最大金额。

4. 返回最大值：return Math.max(max1, max2);：返回两种情况中能偷到的最多的钱。

5. 线性偷窃函数：

   • private int robLinear(int[] nums, int start, int end)：这个方法用来处理线性房子的问题，只需要给定开始和结束的索引。
   • 在这个方法中，使用 prev1 和 prev2 来保存前两个状态的最大值。

6. 循环计算：

   • for (int i = start; i <= end; i++)：从 start 到 end 遍历每个房间。
   • int current = Math.max(prev2, nums[i] + prev1);：计算当前能偷到的最多钱。
   • 更新 prev1 和 prev2 的值，为下一个房间准备。

7. 返回结果：最后返回 prev2，它保存的是最多的金额。

8. 主函数：

   • 在 main 方法中，我们测试了几个例子，打印出能偷到的最大金额。

示例说明

• 输入 [1, 2, 3, 4]：

  • 最优方案是偷第2（2元）和第4（4元）个房间，总共是6。

• 输入 [1, 3, 6]：

  • 最优方案是偷第3个房间，总共是6。

• 输入 [2, 10, 5]：

  • 最优方案是偷第2个房间，总共是10。

• 输入 [5, 1, 2, 10, 6]：

  • 最优方案是偷第1（5元）和第4（10元）个房间，总共是15。

希望这篇文章对你有帮助👍。