打家劫舍 II · 把环拆成两条线
环形房子的唯一难点：第 0 间和最后一间也相邻
先看清楚它和 LC198 的区别，再理解为什么最优解不可能同时偷首尾，于是把环剪成“去尾”“去首”两条线性数组，各跑一遍 robRange 取 max。
题目在问什么
- 有一圈房子，每个房子有金额。
- 不能偷相邻房子，一偷相邻就报警。
- 和 LC198 不同的是：第 0 间房和最后一间房也相邻。
- 目标是在不报警的情况下偷到最大金额。
首尾两个 2 在环里是相邻的， 不能同时偷。所以哪怕它们加起来是 4，也只能放弃， 改偷中间的 3。
最大金额 = 3（只偷中间那间）。
为什么不能直接套 LC198
一条直路，首尾不相邻， 房 0 和房 2 互不影响，可以同时偷。
首尾接上了，房 0 和房 2 也相邻， 不能同时偷。
建模过程：把环拆成两条线
关键观察：最终方案一定不能同时包含首和尾。 既然如此，就按“到底放弃谁”分成两种情况：
砍掉尾，剩下一条直线，首尾不再相邻 → 就是普通 LC198。
砍掉首，剩下一条直线，首尾不再相邻 → 也是普通 LC198。
两段分别当成 LC198 来做，最后 answer = max(robRange(A), robRange(B))。
边界测试 · 切换后整段动画会重算
第一幕 · 环形房子登场
把数组弯成环，额外多出一条 房4 → 房0 的相邻关系。
这一排房子 nums = [2, 7, 9, 3, 1] 首尾接成了一圈。注意那条红线：第 0 间和第 4 间也相邻——这正是它和 LC198 唯一的区别。
时间线 · 点击跳转
代码 · 当前高亮行随帧切换
1func rob(nums []int) int {2 n := len(nums)34 if n == 1 {5 return nums[0]6 }78 return max(9 robRange(nums, 0, n-2),10 robRange(nums, 1, n-1),11 )12}1314func robRange(nums []int, start, end int) int {15 pre := 016 cur := 01718 for i := start; i <= end; i++ {19 next := max(cur, pre+nums[i])20 pre = cur21 cur = next22 }2324 return cur25}2627func max(a, b int) int {28 if a > b {29 return a30 }31 return b32}
- rob 只负责拆环rob 不做 DP，它只判断 n==1 的边界，然后把环拆成两条线，调用两次 robRange 再取 max。
- robRange 负责解决一条线上的 LC198robRange(nums, start, end) 就是在闭区间 [start, end] 上原样跑一遍 LC198 打家劫舍。
- pre 表示前前一间房的最大收益对应 LC198 的 prev2：偷当前房时只能接到 pre 上，因为相邻的前一间不能碰。
- cur 表示前一间房的最大收益对应 LC198 的 prev1：不偷当前房时，收益直接沿用 cur。
- next = max(cur, pre + nums[i]) 表示偷或不偷当前房子的最大值不偷取 cur，偷取 pre + nums[i]，两者取大就是处理完当前房后的最优；随后滚动 pre ← cur、cur ← next。
robRange 跑一趟是 O(n)，rob 一共调用两趟，总共 O(2n)，去掉常数仍是 O(n)。
robRange 只用 pre、cur 两个滚动变量，不开 dp 数组；rob 也只存两趟的返回值，所以空间是 O(1)。
n 是房子数量。
- ① 任何合法方案都不含首尾对：房 0 和房 n-1 在环里相邻，所以最优解最多包含其中一个。
- ② 按放弃谁分两类，恰好穷尽：不含尾的方案全在 A=nums[0..n-2] 里；不含首的方案全在 B=nums[1..n-1] 里。 这两类合起来覆盖了所有“不同时含首尾”的方案。
- ③ 首尾都不偷无需单列：这种方案同时是 A、B 的合法解，A、B 各自取最大值时早已把它算进去，所以不会漏。
- ④ 每条线就是 LC198：砍掉一端后首尾不再相邻，robRange 在直线上求最优是已被证明正确的线性 DP， 取 max 即环形最优。
- robRange 内：每处理完一间房，cur 恒等于 “这条线从区间左端到当前房为止”能偷到的最大金额，pre 比它慢一拍。 所以循环结束时 cur 就是整条线的全局最优。
- 环形层面：答案 = max(A 趟最优, B 趟最优)，始终是一个不同时偷首尾的合法值， 因此永远不会触发警报。
- 只跑一趟 LC198 把整圈当线性，可能同时选中首尾两间，得到非法方案。
- 忘了 n==1 的特判：robRange(nums, 0, n-2) 会变成 robRange(nums, 0, -1)。
- 误以为还要单独算“首尾都不偷”，其实它已经被 A、B 两段各自的 DP 覆盖了。
- 把两段的区间写错：A 是去掉最后一间 [0, n-2]，B 是去掉第一间 [1, n-1]。
- robRange 内部把 pre、cur 的滚动顺序写反，next 还没用就被覆盖。
- 这题是 LC198 打家劫舍的环形版本，唯一区别是第 0 间和最后一间也相邻。
- 首尾相邻意味着它们不能同时偷，所以最优方案一定落在“不偷首”或“不偷尾”两种情况里。
- 于是把环剪成两条线性数组：A = nums[0..n-2]（去掉尾），B = nums[1..n-1]（去掉首）。
- 两段分别当成 LC198 跑 robRange，最后 max(robRange A, robRange B) 就是答案。
- robRange 里 pre/cur 是滚动变量，next = max(cur, pre + nums[i]) 就是偷或不偷取大。
- 注意 n==1 要特判直接返回 nums[0]，否则 robRange(0, -1) 会越界。
这题和 LC198 有什么区别？
LC198 是直线，首尾不相邻；LC213 首尾接成环，第 0 间和最后一间也相邻。
为什么首尾不能同时选？
环里它们相邻，同时偷会触发警报，是非法方案。
为什么拆成 [0..n-2] 和 [1..n-1]？
最优解不含首尾对，按去尾 / 去首分两类恰好穷尽所有合法情况。
robRange 里 pre、cur、next 是什么？
pre = 前前一间最优，cur = 前一间最优，next = max(cur, pre+nums[i]) = 偷或不偷取大。
面试 30 秒怎么讲？
环 = 首尾相邻 → 拆成去尾、去首两条线 → 各跑 LC198 的 robRange → 取 max；记得 n==1 特判。
直线版，robRange 就是它的滚动写法；LC213 直接复用。
房子排成二叉树，相邻变父子，用后序遍历返回 [偷, 不偷] 两个值。