LeetCode 213. 打家劫舍 II
目录
题目描述
题意分析
一排房屋每间存有一定金额，
nums[i]就是第i间房的钱。要求选出若干间房把钱拿走，使总额最大。限制只有一条：相邻的两间房不能同时被选，否则会触发报警。
与最基础的那道抢劫题相比，这里多了一个新约束——所有房屋围成一圈，第一间和最后一间也是相邻的。也就是说
nums[0]与nums[n - 1]同样不能同时入选，这是整道题唯一新增的信息。边界方面要留意：
n可能等于 1。此时整个圈只有一间房，它和自己不构成相邻冲突，答案就是nums[0]。金额均为非负数，所以「一间都不选」的方案价值为 0，永远不会比最优解更好。
解法：拆环后线性动态规划
核心思路
问题关键：普通打家劫舍只限制相邻房屋，环形版本额外让第一间和最后一间相邻。难点不在转移，而在防止首尾同时被选。
为什么拆成两个线性问题：任意合法方案至少满足“没选第一间”或“没选最后一间”。因此只需分别求区间
[1, n - 1]与[0, n - 2]的线性最优值，再取较大者。两类允许在“首尾都不选”处重叠，因为求最大值不会重复累加。在线性区间中，维护：
preOne：处理到前一间房时的最大金额；preTwo：处理到前两间房时的最大金额。当前房只有“不偷”和“偷”两种选择，转移为
cur = max(preOne, preTwo + nums[i])。这两个状态在每轮结束后继续向前滚动。正确性：线性转移穷尽了当前房选或不选的全部合法情况，且选择当前房时只接在
i - 2的最优方案后，不会出现相邻房。环形方案又必然属于上述至少一个区间；两个区间的方案都排除了首尾同选。因此二者最大值恰好是环上的最优解。
解题步骤
- 若只有一间房，直接返回其金额，避免拆出空区间。
- 写
robRange(nums, left, right)解决闭区间上的线性问题。- 区间内从左到右计算
max(不偷当前房, 偷当前房)，每轮更新两个历史状态。- 分别计算“放弃最后一间”和“放弃第一间”，返回较大值。
面试口述示例：
[2,3,2]拆成[2,3]和[3,2]，两个线性最优值都是 3，所以答案为 3；不能直接在线性数组上计算，否则可能把首尾两个 2 同时选入。边界反例：
[5]必须特判为 5；[2,1,1,2]若忽略环会得到 4，而拆成两个区间后的答案是 3。
代码实现
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int skipLast = robRange(nums, 0, n - 2);
int skipFirst = robRange(nums, 1, n - 1);
return Math.max(skipLast, skipFirst);
}
private int robRange(int[] nums, int left, int right) {
int preTwo = 0;
int preOne = 0;
for (int i = left; i <= right; i++) {
int cur = Math.max(preOne, preTwo + nums[i]);
preTwo = preOne;
preOne = cur;
}
return preOne;
}
}
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
skipLast := robRange(nums, 0, n-2)
skipFirst := robRange(nums, 1, n-1)
if skipLast > skipFirst {
return skipLast
}
return skipFirst
}
func robRange(nums []int, left int, right int) int {
preTwo, preOne := 0, 0
for i := left; i <= right; i++ {
cur := preOne
if preTwo+nums[i] > cur {
cur = preTwo + nums[i]
}
preTwo, preOne = preOne, cur
}
return preOne
}
复杂度分析
- 时间复杂度：$O(n)$，两个长度不超过 $n$ 的区间各扫描一次。
- 空间复杂度：$O(1)$，线性 DP 只保留前两个状态。
关键点总结
- 环比直线只多了首尾冲突；固定放弃其中一端，就能复用线性打家劫舍。
- 两个区间不必互斥，只需覆盖全部合法方案；取最大值时重复覆盖不会影响答案。
preTwo和preOne始终对应更新前的dp[i-2]、dp[i-1]，因此必须先算cur再滚动。- 若面试官要求一次 DP，也可以把“首房是否选择”加入状态，但两次线性扫描更短、更不易错。
易错点总结
- 直接对整个数组做线性 DP：
[2,1,1,2]会非法地同时选择首尾，得到 4。- 漏掉
n == 1：两个拆分区间都会为空，[5]会错成 0。- 区间边界仍同时包含首尾：
[0, n - 1]不是有效的拆环结果。- 滚动前先覆盖
preTwo或preOne：当前转移会读取新值，等价于允许选择相邻房。- 把拆分误解成“必须恰好放弃一个端点”：首尾都不选同样合法，两个区间只是限制可选范围，并不强制选择端点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 线性数组上的相邻互斥基础 DP |
| 337. 打家劫舍 III | 中等 | 把相邻互斥搬到二叉树上做树形 DP |
| 740. 删除并获得点数 | 中等 | 按值域重建数组后转化为相邻互斥 |
| LCR 089. 打家劫舍 | 中等 | 同 198 的线性版本，可作滚动数组练手 |
| LCR 090. 打家劫舍 II | 中等 | 与本题同构的环形拆分 |
| 面试题 17.16. 按摩师 | 简单 | 相邻互斥的最简入门形式 |