环形房屋打家劫舍 II（进阶版：房屋形成环，不能偷相邻房屋，求最大可偷金额）

1. 题目描述

我们有一个环形排列的房屋，每个房屋里都有一定金额的现金。你作为一名专业的小偷，计划偷窃这些房屋。但是，相邻的房屋装有相连的安防系统，如果两间相邻的房屋在同一晚上被偷，系统会自动报警。

给定一个整数数组 nums，表示每个房屋的金额（nums[i] >= 0），房屋围成一个环，即第一个房屋和最后一个房屋相邻。请计算在不触动警报的情况下，你今晚能够偷窃到的最高总金额。

示例：

• 输入：nums = [2, 3, 2]
• 输出：3
• 解释：因为房屋围成环，你不能同时偷第一个房屋（金额 2）和最后一个房屋（金额 2），所以最大金额为偷第二个房屋（金额 3）。

2. 问题分析

这个问题的核心限制是：

1. 不能偷相邻的房屋（在数组中表现为不能选择相邻的元素）。
2. 房屋成环，所以第一个元素和最后一个元素也被视为相邻。

如果我们把环断开，就变成了两个线性问题：

• 情况1：只考虑从第 1 间到第 n-1 间房屋（即不偷最后一间），因为最后一间与第一间相邻，不能同时偷。
• 情况2：只考虑从第 2 间到第 n 间房屋（即不偷第一间），理由同上。

最终的答案就是这两种情况中的较大值。

接下来，我们只需要解决 线性版本 的房屋打家劫舍问题即可。

3. 线性房屋打家劫舍的解法（基础动态规划）

对于线性排列的房屋 nums[0..n-1]（n 为房屋数量），我们定义：

• dp[i]：表示从第 0 间到第 i 间房屋（包括第 i 间）中，能偷到的最大金额。

状态转移方程：

对于第 i 间房屋，我们有两种选择：

1. 偷第 i 间：那么就不能偷第 i-1 间，所以总金额为 nums[i] + dp[i-2]。
2. 不偷第 i 间：那么总金额为 dp[i-1]。

因此：

\[dp[i] = \max(dp[i-1], \: nums[i] + dp[i-2]) \]

边界条件：

• 当 i = 0 时，只有一个房屋，dp[0] = nums[0]。
• 当 i = 1 时，有两个房屋，不能都偷，所以 dp[1] = max(nums[0], nums[1])。

最终，dp[n-1] 就是线性问题的答案。

4. 将线性解法应用到环形房屋

对于环形房屋 nums[0..n-1]：

• 情况1（不偷最后一间）：计算线性数组 nums[0..n-2] 的最大金额。
• 情况2（不偷第一间）：计算线性数组 nums[1..n-1] 的最大金额。

特殊情况：

• 如果只有一个房屋（n = 1），那么只能偷这一间，直接返回 nums[0]。
• 如果有两个房屋（n = 2），因为是环形，不能同时偷两间，所以返回 max(nums[0], nums[1])。

对于 n >= 3 的情况，分别计算两个线性子问题的答案，取最大值。

5. 逐步计算示例

以 nums = [2, 3, 2] 为例：

1. 基本情况判断：n = 3，大于 2，所以需要分两种情况。

2. 情况1：不偷最后一间（考虑 nums[0..1] = [2, 3]）

   • 线性 DP：
     • dp[0] = 2
     • dp[1] = max(2, 3) = 3
     • 结果：max_amount1 = 3

3. 情况2：不偷第一间（考虑 nums[1..2] = [3, 2]）

   • 线性 DP：
     • dp[0] = 3（这里 dp[0] 对应原始数组的 nums[1]）
     • dp[1] = max(3, 2) = 3
     • 结果：max_amount2 = 3

4. 最终结果：max(3, 3) = 3

6. 优化空间复杂度

在线性 DP 中，我们注意到 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，因此可以用两个变量滚动更新，将空间复杂度从 O(n) 降到 O(1)。

线性打家劫舍函数（O(1) 空间）的伪代码：

function rob_linear(nums, start, end):
    prev2 = 0   // 表示 dp[i-2]
    prev1 = 0   // 表示 dp[i-1]
    for i from start to end:
        current = max(prev1, nums[i] + prev2)
        prev2 = prev1
        prev1 = current
    return prev1

这样，我们可以在 O(n) 时间和 O(1) 空间内解决环形问题。

7. 完整算法步骤

1. 如果 nums 长度为 1，返回 nums[0]。
2. 如果 nums 长度为 2，返回 max(nums[0], nums[1])。
3. 否则：
   • 调用 rob_linear(nums, 0, n-2) 得到 max_amount1（不偷最后一间）。
   • 调用 rob_linear(nums, 1, n-1) 得到 max_amount2（不偷第一间）。
4. 返回 max(max_amount1, max_amount2)。

8. 复杂度分析

• 时间复杂度：O(n)。我们两次遍历数组，每次 O(n)。
• 空间复杂度：O(1)。只用了几个变量存储中间结果。

9. 示例验证

示例 1：nums = [1, 2, 3, 1]

• 情况1（不偷最后一间）：[1, 2, 3] → 线性最大为 1+3=4。
• 情况2（不偷第一间）：[2, 3, 1] → 线性最大为 2+1=3。
• 最终结果：max(4, 3) = 4。

示例 2：nums = [0]

• 直接返回 0。

示例 3：nums = [5, 1, 2, 6, 3]

• 情况1（不偷最后一间）：[5, 1, 2, 6] → 线性最大为 5+6=11。
• 情况2（不偷第一间）：[1, 2, 6, 3] → 线性最大为 1+6=7。
• 最终结果：max(11, 7) = 11。

通过以上步骤，我们就能高效地解决环形房屋打家劫舍问题。核心思路是将环形拆分为两个线性子问题，并利用动态规划（可优化为 O(1) 空间）分别求解。