1. 问题概述：理解环形房屋的打劫难题
LeetCode 213题"House Robber II"是经典动态规划问题"打家劫舍"的进阶版本。与基础版不同之处在于，这里的房屋排列成环形——即第一间房和最后一间房相邻。这个看似微小的改动彻底改变了问题的性质，使得我们不能简单套用原始问题的解法。
在实际场景中，这个问题可以类比为银行金库的环形安保系统，或者商场夜间巡逻的路线规划。盗贼需要在不触发相邻警报的情况下最大化收益，而环形布局意味着选择第一个目标会直接影响最后一个目标的可行性。
2. 核心思路拆解：环形问题的转化技巧
2.1 环形结构的处理关键
面对环形排列的房屋，我们需要意识到一个核心特性：首尾房间不能同时被抢。这提示我们可以将环形问题分解为两个线性问题：
- 不抢最后一间房（即只考虑房屋[0...n-2]）
- 不抢第一间房（即只考虑房屋[1...n-1]）
然后取这两个子问题的最大值作为最终解。这种"分而治之"的策略是处理环形问题的常用技巧。
提示：这种分解方法保证了首尾房间永远不会同时出现在同一个子问题中，完美规避了环形带来的约束。
2.2 动态规划状态定义
对于每个线性子问题，我们沿用标准打家劫舍的动态规划思路：
定义dp[i]表示前i间房屋能获得的最大金额，状态转移方程为：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])这表示对于第i间房屋，我们有两种选择：
- 不抢它：最大金额保持为dp[i-1]
- 抢它：最大金额为dp[i-2]加上当前房屋金额
3. 完整算法实现与优化
3.1 基础实现代码
def rob(nums): if len(nums) == 1: return nums[0] def linear_rob(sub_nums): prev, curr = 0, 0 for num in sub_nums: prev, curr = curr, max(curr, prev + num) return curr return max(linear_rob(nums[:-1]), linear_rob(nums[1:]))3.2 空间复杂度优化
注意到dp[i]只依赖于dp[i-1]和dp[i-2]，我们可以将空间复杂度从O(n)优化到O(1)，仅用两个变量滚动计算：
def linear_rob(sub_nums): prev, curr = 0, 0 for num in sub_nums: prev, curr = curr, max(curr, prev + num) return curr3.3 边界条件处理
特殊情况的处理往往决定代码的鲁棒性：
- 单元素数组：直接返回该元素
- 双元素数组：返回较大的那个
- 空数组：返回0（但LeetCode测试用例中不会出现）
4. 复杂度分析与变种思考
4.1 时间复杂度
算法需要处理两个子问题，每个子问题都是O(n)的线性扫描，因此总时间复杂度为O(n)。由于两个子问题可以顺序处理，空间复杂度保持为O(1)。
4.2 相似问题变种
- House Robber III：房屋排列成二叉树结构
- Circular Subarray Sum：环形数组的最大子数组和
- Paint House II：相邻约束下的最小成本问题
5. 常见错误与调试技巧
5.1 典型错误模式
- 直接套用原始解法：忽略环形约束，导致首尾同时被选
# 错误示例 def rob(nums): prev, curr = 0, 0 for num in nums: prev, curr = curr, max(curr, prev + num) return curr # 没有处理环形情况错误处理单元素情况：忘记特殊处理len(nums)==1的情况
子数组切片错误：错误地使用nums[1:-1]而不是nums[1:]
5.2 调试建议
从小测试用例开始验证：
- [2,3,2] → 应返回3
- [1,2,3,1] → 应返回4
- [0] → 应返回0
打印子问题计算结果：
print(linear_rob(nums[:-1]), linear_rob(nums[1:]))- 可视化dp数组的变化过程，确认状态转移正确
6. 实战优化与进阶思考
6.1 代码可读性优化
使用更具表达力的变量名：
def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] def max_gain(houses): prev_prev, prev = 0, 0 for house in houses: current = max(prev, prev_prev + house) prev_prev, prev = prev, current return prev return max(max_gain(nums[:-1]), max_gain(nums[1:]))6.2 数学证明思路
可以严格证明这种分解方法的正确性：
- 设最优解为S
- 若S不包含nums[0]，则S等于linear_rob(nums[1:])
- 若S不包含nums[-1]，则S等于linear_rob(nums[:-1])
- 因此S必然是这两个值的较大者
6.3 扩展到其他环形问题
这种"破环为链"的技巧可以应用于：
- 环形数组的最大子数组和
- 环形调度问题
- 环形缓冲区处理
在解决环形问题时，首先考虑如何将其转化为线性问题通常是突破口。
