LeetCode LCR 090. 打家劫舍 II
题目描述
题意分析
房屋围成一圈，相邻两间不能同时选择，第一间和最后一间也相邻。要求在这个限制下取得最大金额。
当房屋至少有两间时，任意合法方案都至少放弃首尾中的一间。因此可以分别在“排除最后一间”和“排除第一间”的两个线性区间中求最优，再取较大值。
解法：拆成两段线性打家劫舍
核心思路
[!blue]
分别计算
[0, n-2]和[1, n-1]。任何环上的合法方案都包含在至少一个区间的方案集合里；反过来，每个区间都缺少一端，在线性相邻限制下得到的方案也一定不会违反首尾互斥。因此两个最优值取最大，恰好覆盖环上的最优方案。两次计算都不需要强制选择另一端。首尾都不选的方案可能出现在两个区间中，但重复参与取最大值不会改变答案。
在线性区间里，每轮开始时，
f表示上一间不选时的最优前缀收益，g表示上一间被选时的最优前缀收益。处理当前金额x，不选当前可以承接旧的任意状态，所以新f = max(f, g)；选择当前必须承接上一间未选的状态，所以新g = f + x。两个候选分别覆盖当前选与不选的全部可能，每一步都保持相邻互斥，因此扫描完后
max(f, g)就是这段区间的最优值。变量初始都置零用于启动递推；处理第一间后得到“不选为零、选择为其金额”，此后才对应上述真实前缀的两种状态，不必把初始g理解为已经偷了不存在的房屋。更新两个变量时必须使用旧状态。Java 先把新的
f暂存为ff，再用旧f计算g；Go 的并行赋值会先计算所有右侧表达式，再统一赋值。
n == 1时首尾是同一间房，不存在两间之间的冲突，直接返回它的金额。n == 2时两个区间各含一间房，两次计算自然得到两者的较大金额。
解题步骤
- 只有一间房时直接返回其金额。
- 分别在线性区间
[0, n-2]、[1, n-1]上调用子过程。- 子过程用旧的
f、g同时计算当前不选和选择的最优值，最终返回两者最大值。- 两个区间的答案取最大值，作为环形问题的结果。
代码实现
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;
int 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的区间各扫描一次。- 空间复杂度：$O(1)$，区间通过下标访问，滚动状态只有常数个变量；Go 的切片视图也不会复制原数组。
关键点总结
[!green]
- 拆分条件是“排除一端”，不是“必须选择另一端”，两组方案合起来覆盖全部合法选择。
- 两个区间有重叠不影响取最大值，单间房则必须在拆分之前单独处理。
- 当前选择状态只能由旧的不选状态转移，先覆盖旧值会错误允许相邻两间同时被选。
易错点总结
[!yellow]
- 环上首尾相邻，分别排除首家或尾家做两次线性问题；不必强制选择某一端。
- 单家先特判，避免拆成两个空区间。
- 滚动更新时保留旧的不偷状态，不能把刚更新的值拿去计算新偷状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 本题通过分别排除首项和末项，转化为两次线性打家劫舍。 |
| 740. 删除并获得点数 | 中等 | 同样化为相邻类别不能同时选择，原题先按数值聚合收益，本题邻接来自环形位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！