LeetCode LCR 090. 打家劫舍 II
目录
题目描述
题意分析
与线性版打家劫舍相比只改了一处：所有房屋围成一圈，第一间和最后一间也是相邻的。仍然不能偷相邻的两家，求最大金额。
环形带来的唯一新增约束就是「首尾不能同时被偷」。除此之外，圈上任何两家的相邻关系与排成一行时完全一致。把这一点看清楚，题目就从「环上的 DP」退化成了「加一条互斥约束的线性 DP」，难度大幅下降。
关键推理是对第一间房做分类讨论：要么不偷第一间，那么最后一间的限制就消失了，可选范围是
nums[1..n-1]这段线性区间；要么偷第一间，那么最后一间必然不能偷，可选范围是nums[0..n-2]这段线性区间。两种情况覆盖了全部合法方案，取较大者即为答案。
注意第二种情况我们说的是「可选范围是
nums[0..n-2]」而非「必须偷第一间」。这是一个容易被质疑的松弛：nums[0..n-2]上的最优解可能并不包含nums[0]。但这不影响正确性——它只是把「不偷首也不偷尾」的方案在两次计算里各算了一遍，而这些方案本来就是合法的，重复计算不会引入非法解，也不会漏掉任何解，取 max 后结果依然正确。能主动说清这一点，是本题面试中的关键得分位。
约束：
1 ≤ nums.length ≤ 100，0 ≤ nums[i] ≤ 1000。长度为 1 是必须特判的边界——此时首尾是同一间房，拆区间会得到[0, -1]这种空区间，两边都返回 0，答案会错成 0 而不是nums[0]。长度为 2 时两段各只有一个元素，自然得到max(nums[0], nums[1])，无需额外处理。
解法：动态规划递推
核心思路
直接在环上做 DP 会遇到麻烦：递推到最后一间时，能不能偷取决于第一间的选择，而第一间的决策发生在递推的最开头，信息已经丢失。这就是环形结构破坏无后效性的典型表现——首尾之间存在一条「远距离」依赖。
常见的补救办法是把「第一间偷没偷」塞进状态，变成二维 DP。但更简洁的观察是：这个额外维度只有两种取值，与其在状态里带着它跑完全程，不如把它提到最外层，枚举两次。
于是问题被拆成两个互不相干的线性子问题：在区间
[0, n-2]上做一次普通打家劫舍，在区间[1, n-1]上再做一次，答案取两者最大值。两次调用之间没有任何耦合，环形的麻烦被彻底消除。
线性子问题用滚动变量实现。设扫描到某间房时，
f表示「上一间房不偷时前缀的最大收益」，g表示「上一间房偷了时前缀的最大收益」。处理当前房屋x时：新的「偷了当前」的值必须建立在「上一间不偷」之上，即g' = f + x；新的「不偷当前」的值可以承接上一间的任意状态，即f' = max(f, g)。要维持的不变量是：每一轮结束后f与g分别是「当前这间不偷」与「当前这间偷了」两种情形下的最优前缀收益。区间扫完后返回max(f, g)。
两个变量的初值都是 0，对应「还没处理任何房屋」，此时两种情形收益都为 0，语义自洽。
解题步骤
- 先特判长度为 1：
n == 1时直接返回nums[0]。这不是可选的优化——环上只有一间房时它不与任何房屋相邻，而拆区间会产生[0, -1]与[1, 0]两个空区间，双双返回 0，答案彻底错误。
- 拆成两段线性区间各求一次：
rob(nums, 0, n - 2)对应「放弃最后一间」，rob(nums, 1, n - 1)对应「放弃第一间」。两段的并集覆盖了所有合法方案，交集（首尾都不偷的方案）被重复计入但不影响取 max 的结果。
- 返回两者较大值：
Math.max(...)。这一步就是对「第一间偷不偷」这个二值维度的枚举。
- 子过程用两个滚动变量：
f是「上一间不偷」的最优值，g是「上一间偷了」的最优值，初值均为 0。用两个变量而不是数组，是因为线性 DP 只回看一格。
- 更新顺序必须借助临时变量：
int ff = Math.max(f, g);先把新的f算好存起来，再执行g = f + nums[l]（此处f仍是旧值，正是我们需要的），最后f = ff。若先赋值f = Math.max(f, g)再算g，右侧用到的就是本轮刚更新的f，等于允许了相邻同偷。Go 版用f, g = max(f, g), f+x的并行赋值天然规避了这个陷阱——右侧全部在赋值前求值。
- 子过程返回
max(f, g)：区间处理完后，最后一间偷或不偷都可能是最优，两者取大。
以
nums = [2, 3, 2]走一遍，n = 3，答案应为 3（首尾都是 2 但相邻，不能同偷，所以只能取中间的 3）。
第一次调用
rob(nums, 0, 1)，扫描[2, 3]。初始f = 0、g = 0。处理 2：ff = max(0, 0) = 0，g = 0 + 2 = 2（偷了这间），f = 0（不偷这间）。处理 3：ff = max(0, 2) = 2，g = f旧 + 3 = 0 + 3 = 3（偷 3 必须上一间不偷，而上一间不偷的最优值是 0），f = 2。返回max(2, 3) = 3。
第二次调用
rob(nums, 1, 2)，扫描[3, 2]。初始f = 0、g = 0。处理 3：ff = 0，g = 0 + 3 = 3，f = 0。处理 2：ff = max(0, 3) = 3，g = f旧 + 2 = 0 + 2 = 2，f = 3。返回max(3, 2) = 3。
两者取大得 3。注意第二次调用里
g = 2表示「偷最后那间 2」的方案只能得 2，因为它逼着放弃了 3；而f = 3表示「不偷最后那间」时可以保留 3。取 max 正确地选出了后者。
再用
nums = [1, 2, 3, 1]核对：rob(0, 2)在[1,2,3]上得max(1+3, 2) = 4，rob(1, 3)在[2,3,1]上得max(2+1, 3) = 3，答案 4，与预期一致。若漏掉n == 1的特判，nums = [5]会走进rob(nums, 0, -1)与rob(nums, 1, 0)，两个空区间都返回 0，输出 0 而非 5。
代码实现
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// 只有一间房时首尾是同一间，拆区间会得到空区间，必须特判。
if (n == 1) {
return nums[0];
}
// 左：放弃最后一间；右：放弃第一间。两者覆盖全部合法方案。
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
// 在线性区间 [l, r] 上做普通打家劫舍。
// f：上一间不偷时的最优值；g：上一间偷了时的最优值。
private int rob(int[] nums, int l, int r) {
int f = 0, g = 0;
for (; l <= r; ++l) {
// 先把新的 f 算出来暂存，右式里的 f 必须还是旧值。
int ff = Math.max(f, g);
g = f + nums[l];
f = ff;
}
return Math.max(f, g);
}
}
func rob(nums []int) int {
n := len(nums)
// 只有一间房时首尾是同一间，拆区间会得到空区间，必须特判。
if n == 1 {
return nums[0]
}
// 左：放弃最后一间；右：放弃第一间。两者覆盖全部合法方案。
return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1))
}
// 在线性区间 [l, r] 上做普通打家劫舍。
// f：上一间不偷时的最优值；g：上一间偷了时的最优值。
func robRange(nums []int, l, r int) int {
f, g := 0, 0
for _, x := range nums[l : r+1] {
// 并行赋值：右侧全部用旧值求值，天然避免了顺序陷阱。
f, g = max(f, g), f+x
}
return max(f, g)
}
复杂度分析
- 时间复杂度：$O(n)$，两段区间长度均为
n - 1，各扫一遍，合计不到2n次常数操作。- 空间复杂度：$O(1)$，只用了
f、g两个滚动变量和若干下标，与输入规模无关。相比线性版的数组写法，这是把「只回看一格」这条性质用到底的结果。
关键点总结
- 环形结构的通用破解思路是「找出那条唯一的远距离约束，然后按它的取值枚举成若干个线性子问题」。本题的远距离约束是首尾互斥，取值只有两种，所以跑两遍线性 DP 即可。这个套路在环形数组的最大子数组和、环形不相邻选取等题上反复出现。
- 两段区间的重叠不是 bug：「首尾都不偷」的方案在两次计算中各出现一次，但重复计入合法解不会破坏取最大值的正确性。面试中主动解释这一点，比只会写代码更能体现对正确性的把握。
n == 1必须特判，因为拆分假设了首尾是两间不同的房。凡是把一个结构拆成子结构来处理，都要先检查「结构小到无法拆分」的退化情形。- 滚动变量的更新顺序是手写 DP 的高频坑：Java 必须用临时变量固定住旧值，Go 的并行赋值则天然安全。写之前先问一句「右侧引用的是本轮还是上轮的值」。
- 两个状态变量的语义要一句话说清（
f是上一间不偷、g是上一间偷了），语义清楚了转移式自然就写对了；语义含糊时才会纠结「到底该用f还是g」。
易错点总结
- 漏掉
n == 1的特判：nums = [5]会拆出两个空区间，返回 0 而不是 5。- 区间写成
rob(nums, 0, n - 1)与rob(nums, 1, n - 1)：nums = [2,3,2]的第一次调用会覆盖整圈，算出2 + 2 = 4，等于同时偷了相邻的首尾。- Java 里先写
f = Math.max(f, g);再写g = f + nums[l];：nums = [2,3,2]的第一段会算成2 + 3 = 5，相邻两间被同时偷。- 子过程返回
g而不是max(f, g)：nums = [1,2,3,1]的第一段[1,2,3]会返回「必须偷最后一个」的 4，看似正确，但在[3,1]上会返回 1 而不是 3。- 子过程返回
f而不是max(f, g)：nums = [2]这类单元素区间会返回 0，因为「不偷最后一间」的分支忽略了唯一的房屋。- 两个变量初值设成
nums[l]之类的具体值：nums = [1,2,3,1]会把第一间重复计入，第一段算出 5 而不是 4。- 在环上直接做一维 DP 而不拆分，只在最后判一次首尾冲突：
nums = [5,1,1,5]的一维 DP 会得到 10（同时偷首尾），事后再减去某一个变成 5，但正确答案是max(5+1, 1+5) = 6，事后修补无法还原正确的中间决策。- 拆分时误以为「偷第一间」的那一段必须强制包含
nums[0]：nums = [1,9,1,9]若强制偷nums[0]，第一段只能得1 + 1 = 2，最终答案错成 9 而不是正确的 18。- Go 里把并行赋值拆成两行：
f = max(f, g)后再g = f + x，与 Java 的顺序错误同源，nums = [2,3,2]输出 5。- 误以为可以只跑
[1, n-1]一段：nums = [9,1,1,1]会漏掉「偷第一间」的最优解9 + 1 = 10，只得到1 + 1 = 2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 213. 打家劫舍 II | 中等 | 与本题完全同题，代码可原样提交 |
| 198. 打家劫舍 | 中等 | 线性排列无首尾约束，是本题内层子过程的原型 |
| LCR 089. 打家劫舍 | 中等 | 与 198 同题，可对照体会「环拆成两段线性」这一步的必要性 |
| 337. 打家劫舍 III | 中等 | 结构换成二叉树，改为后序遍历返回「偷/不偷」两个值的树形 DP |
| 918. 环形子数组的最大和 | 中等 | 同样是环形拆解，但手法是「总和减去最小子数组和」而非枚举首元素 |
| 740. 删除并获得点数 | 中等 | 需先把原数组按数值聚合成价值数组，再套线性打家劫舍，考察问题转化 |
| 面试题 17.16. 按摩师 | 简单 | 线性不相邻选取的最简形态，适合单独练滚动变量的更新顺序 |
| 45. 跳跃游戏 II | 中等 | 同为一维决策序列，但最优子结构可用贪心区间覆盖代替 DP |