LC213. 打家劫舍II

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 示例 1： 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。 示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 3： 输入：nums = [0] 输出：0 提示： 1 <= nums.length <= 100 0 <= nums[i] <= 1000

题目解析

题目在说什么

想象一下，你是一个小偷，面前有一圈房子，每个房子里都有一些钱。但是，这些房子装了警报系统：如果你偷了相邻的两间房子，警报就会响。现在房子是围成一圈的，所以第一个房子和最后一个房子也算相邻。你要在不触发警报的情况下，偷到最多的钱。

比如，房子里的钱是 [2,3,2]，因为围成一圈，你不能同时偷第一个和最后一个（它们是相邻的），所以只能偷中间的3，或者偷第一个和最后一个中的某一个，但偷第一个就不能偷第二个，偷最后一个就不能偷第一个，所以最优是偷中间的3，得到3元。

再比如 [1,2,3,1]，你可以偷第一个和第三个（1+3=4），或者偷第二个和第四个（2+1=3），或者只偷一个，最优是4。

如果只有一个房子 [0]，那就只能偷0元。

思路是怎么来的

这个问题和普通的“打家劫舍”不一样，普通版本是直线排列的房子，你只需要考虑相邻不能偷。但这里是环形，第一个和最后一个也相邻，这就多了一个限制。

生活化比喻：假设你有一排房子，但它们是围成一个圈的。你站在圈外，想偷钱，但有个规则：不能偷相邻的。如果只是直线，你可以从左边开始，一个一个考虑偷不偷。但现在是环形，第一个和最后一个也相邻，所以你不能同时偷它们两个。

怎么解决这个环形问题呢？ 一个聪明的办法是：把环形拆成两个直线问题。

• 情况一：不偷第一个房子。这样，最后一个房子就可以随便偷（因为第一个没偷，最后一个和第一个不冲突），但要注意最后一个和倒数第二个不能同时偷。这相当于我们只考虑从第二个房子到最后一个房子这一条直线。
• 情况二：不偷最后一个房子。这样，第一个房子就可以随便偷，但要注意第一个和第二个不能同时偷。这相当于我们只考虑从第一个房子到倒数第二个房子这一条直线。

然后，我们分别计算这两种情况下能偷到的最大金额，取较大的那个，就是答案。

为什么这样可行？因为环形问题的核心矛盾就是首尾不能同时偷。我们通过“排除”其中一个，就变成了普通的直线问题。而直线问题我们已经知道怎么用动态规划解决（就是经典的“打家劫舍”问题）。

代码逐步拆解

我们来看参考代码，它把问题分成了两步：

1. 处理环形：生成两个子数组，一个排除第一个房子，一个排除最后一个房子。 2. 用动态规划解决直线问题：写一个函数 myRob，专门处理直线排列的房子。

第一步：处理环形

int n = nums.length;
if(n == 0) return 0;
if(n == 1) return nums[0];

• 如果数组为空，没有房子，返回0。
• 如果只有一个房子，直接偷它，返回它的金额。

int[] numsExceptFirstRoom = Arrays.copyOfRange(nums, 1, nums.length);
int[] numsExceptLastRoom = Arrays.copyOfRange(nums, 0, nums.length - 1);

• numsExceptFirstRoom：从索引1开始到末尾，即排除第一个房子。
• numsExceptLastRoom：从索引0开始到倒数第二个，即排除最后一个房子。

return Math.max(myRob(numsExceptFirstRoom), myRob(numsExceptLastRoom));

• 分别对这两个子数组调用 myRob，得到两个最大金额，取最大值。

第二步：直线动态规划函数 myRob

这个函数解决的是：一排房子，不能偷相邻的，求最大金额。

int n = nums.length;
int[] value = new int[n + 1];

• value[i] 表示前 i 个房子（即索引0到i-1）能偷到的最大金额。
• 长度是 n+1，因为我们要从0开始到n。

value[0] = 0;
value[1] = nums[0];

• 前0个房子：没有房子，金额0。
• 前1个房子：只能偷第一个房子，金额就是 nums[0]。

for(int i = 2 ; i <= n ; i++){
    value[i] = Math.max(value[i - 1], value[i - 2] + nums[i - 1]);
}

• 从第2个房子开始考虑（i=2对应索引1的房子）。
• 对于第i个房子（索引i-1），有两种选择：
• 不偷这个房子：那么最大金额就是前i-1个房子的最大金额，即 value[i-1]。