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

题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。这些房屋围成一圈，即第一个房屋和最后一个房屋相邻。每个房屋都有一定数量的现金，存放在一个整数数组 nums 中，nums[i] 表示第 i 个房屋内的现金金额。相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被偷，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums，请计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 1
输入：nums = [2,3,2]
输出：3
解释：因为房屋围成一圈，所以不能同时偷窃第一个房屋（金额 2）和最后一个房屋（金额 2），只能偷窃第二个房屋（金额 3）。

示例 2
输入：nums = [1,2,3,1]
输出：4
解释：可以先偷窃第一个房屋（金额 1），然后偷窃第三个房屋（金额 3），总金额为 4。注意不能偷窃第一个和最后一个房屋，因为它们相邻。

解题过程

这个问题是经典的“打家劫舍”问题的环形版本。在环形条件下，第一个和最后一个房屋不能同时被偷。我们可以将环形问题拆解成两个线性问题来解决。

步骤 1：问题拆解
由于房屋是环形的，我们可以考虑以下两种情况：

1. 不偷第一个房屋，只考虑从第二个房屋到最后一个房屋（即 nums[1] 到 nums[n-1]）。
2. 不偷最后一个房屋，只考虑从第一个房屋到倒数第二个房屋（即 nums[0] 到 nums[n-2]）。

这样，两种情况都变成了线性排列的房屋，可以使用标准的动态规划方法求解。最终答案是这两种情况的最大值。

步骤 2：定义线性问题的动态规划状态
对于一个线性排列的房屋数组 arr（长度为 m），定义：
dp[i] 表示考虑前 i 个房屋（索引从 0 到 i-1）时，能偷窃到的最高金额。
注意，这里“考虑前 i 个房屋”意味着不一定偷第 i-1 个房屋，而是根据规则选择偷或不偷，使得总金额最大。

状态转移方程：
对于第 i 个房屋（索引为 i-1），有两种选择：

• 不偷这个房屋：则最高金额等于前 i-1 个房屋的最高金额，即 dp[i-1]。
• 偷这个房屋：则不能偷前一个房屋（索引 i-2），因此最高金额为 dp[i-2] + arr[i-1]。

所以转移方程为：
dp[i] = max(dp[i-1], dp[i-2] + arr[i-1])，其中 i ≥ 2。

边界条件：

• dp[0] = 0（没有房屋，金额为 0）。
• dp[1] = arr[0]（只有一个房屋，只能偷它）。

步骤 3：实现线性问题的求解函数
我们可以实现一个辅助函数 linearRob(arr)，它接收一个线性数组 arr，返回按照上述动态规划规则能偷窃到的最高金额。

伪代码：

function linearRob(arr):
    n = len(arr)
    if n == 0: return 0
    if n == 1: return arr[0]
    dp = array of size n+1
    dp[0] = 0
    dp[1] = arr[0]
    for i from 2 to n:
        dp[i] = max(dp[i-1], dp[i-2] + arr[i-1])
    return dp[n]

实际上，由于 dp[i] 只依赖于前两个状态，我们可以用两个变量滚动优化空间复杂度到 O(1)。但为清晰起见，这里先保持数组形式。

步骤 4：处理环形情况
设原数组为 nums，长度为 n。

• 情况 1：不偷第一个房屋，计算 linearRob(nums[1:])（即从索引 1 到 n-1）。
• 情况 2：不偷最后一个房屋，计算 linearRob(nums[:n-1])（即从索引 0 到 n-2）。

注意，如果 n=1，则只有一个房屋，两种情况都会变成空数组，需要特殊处理。我们可以在开始时判断：如果 n=1，直接返回 nums[0]。

最终结果：max(linearRob(nums[1:]), linearRob(nums[:n-1]))。

步骤 5：示例演算
以 nums = [1,2,3,1] 为例：

1. 不偷第一个房屋：考虑子数组 [2,3,1]。
   • dp[0]=0, dp[1]=2
   • dp[2] = max(dp[1], dp[0]+3) = max(2, 0+3) = 3
   • dp[3] = max(dp[2], dp[1]+1) = max(3, 2+1) = 3
     最高金额为 3。
2. 不偷最后一个房屋：考虑子数组 [1,2,3]。
   • dp[0]=0, dp[1]=1
   • dp[2] = max(dp[1], dp[0]+2) = max(1, 0+2) = 2
   • dp[3] = max(dp[2], dp[1]+3) = max(2, 1+3) = 4
     最高金额为 4。
     取最大值 4，与示例输出一致。

步骤 6：边界情况处理

• 如果数组长度为 0，返回 0。
• 如果数组长度为 1，直接返回该元素值（因为环形中只有一个房屋，偷它不会触发警报）。
• 如果数组长度为 2，由于第一个和最后一个相邻，只能偷其中一个，返回 max(nums[0], nums[1])。实际上我们的拆解方法也能处理这种情况。

步骤 7：复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。我们进行了两次线性动态规划，每次 O(n)。
• 空间复杂度：O(1)（如果使用滚动变量优化）或 O(n)（如果使用数组，但可优化）。

总结
环形房屋打家劫舍问题的核心是将环形拆解为两个线性子问题，避免同时考虑首尾房屋。通过分别计算不偷首房和不偷尾房的最大金额，再取最大值，即可得到全局最优解。这个问题很好地体现了区间动态规划中“破环成链”的思想。