BM79. 打家劫舍(二)
题目描述
你是一个经验丰富的小偷，准备偷沿湖的一排房间。这些房间组成一个闭合的圆环， 即第一个房间和最后一个房间视为相邻。仍然不能偷相邻的两家。 给定长度为 n 的整数数组 nums，请你计算在不被发现的前提下最多的偷窃金额。
输入格式
nums：int 型一维数组，表示每个房间的现金数额。
输出格式
返回 int 型，最多能偷到的金额。
示例
示例 1
输入：
nums = [1,2,3,4]
输出：
6
说明： 最优方案是偷第 2、4 个房间，金额 2 + 4 = 6。
示例 2
输入：
nums = [1,3,6]
输出：
6
说明： 由于 1 和 6 相邻，最优方案是只偷第 3 个房间，金额 6。
解题思路
第一步：理解问题本质
和「打家劫舍（一）」相比，唯一的区别是房间排成了一个环： 第一个房间和最后一个房间也相邻。于是多了一条约束 —— 首尾不能同时偷。
第二步：把环拆成两条直线
既然约束只有「首尾不能同时偷」，就可以分情况讨论：
- 情况 A：不偷最后一个房间 → 问题等价于在
nums[0 .. n-2]上做线性打家劫舍； - 情况 B：不偷第一个房间 → 问题等价于在
nums[1 .. n-1]上做线性打家劫舍。
这两种情况已经覆盖了所有合法方案（任何合法方案要么不偷最后一个， 要么不偷第一个）。答案就是两者取最大值。
第三步：复用线性解法
线性打家劫舍就是 BM78 的滚动写法。把它抽成一个辅助函数 _rob_line，
环形版本调用两次即可，代码干净且不易写错。
注意 n == 1 时只有一个房间，「首尾相邻」退化成自己，直接返回 nums[0]。
完整代码实现
算法可视化 · 逐帧回放这道题的代码9 帧 · 录制输入 [1,2,3,4]
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
"""环形打家劫舍：拆成两个线性子问题取最大值"""
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
# 方案一：不考虑最后一个房间；方案二：不考虑第一个房间
return max(self._rob_line(nums[:-1]), self._rob_line(nums[1:]))
def _rob_line(self, arr: List[int]) -> int:
"""线性打家劫舍（辅助方法，下划线开头）"""
prev, cur = 0, 0
for x in arr:
prev, cur = cur, max(cur, prev + x)
return cur
示例推演
以 nums = [1,2,3,4] 为例：
| 方案 | 子数组 | 线性最优解 | 说明 |
|---|---|---|---|
| A：不偷最后一个 | [1,2,3] | max(1+3, 2) = 4 | 偷第 1、3 个 |
| B：不偷第一个 | [2,3,4] | max(2+4, 3) = 6 | 偷第 2、4 个 |
取最大值 6，与答案一致。
再以 nums = [1,3,6] 为例：
| 方案 | 子数组 | 线性最优解 |
|---|---|---|
| A：不偷最后一个 | [1,3] | max(1, 3) = 3 |
| B：不偷第一个 | [3,6] | max(3, 6) = 6 |
取最大值 6，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 拆成两个线性问题 | O(n) | O(1) | 推荐 |
两次线性扫描合起来仍是 O(n)。
易错点总结
1. n == 1 的边界
只有一个房间时，nums[:-1] 和 nums[1:] 都是空数组，
会错误地返回 0。必须特判直接返回 nums[0]。
2. 用「首尾都偷」的贪心
环形的关键就是首尾互斥，不能简单地在原数组上套线性 DP。
3. 只拆一种情况
只去掉首或只去掉尾都不够，必须两种情况取最大。
扩展思考
- 若环被「打断」成两条链（给定某条边不能走），就退化成两个线性问题。
- 更一般的「树上不能偷相邻节点」用树形 DP，思路同样是把选择传给父节点。