LeetCode 198. 打家劫舍
目录
题目描述
题意分析
一排房屋各有一笔金额，要求选出一个金额总和最大的子集，唯一的限制是不能偷相邻的两间。
这个限制把每间房屋都变成一道二选一：偷它，就必须放弃它左边那间；不偷它，左边那间怎么选就完全不受影响。也就是说，每个位置的决策只和它紧邻的历史有关，和更远的房屋没有直接冲突。
约束信号也值得留意：房屋数最多 100、金额非负。金额非负意味着「多考察一间房屋，答案不会变差」，我们要的是「前若干间的最优」而不用担心跳过谁会吃亏。
边界上，只有一间房时直接偷它；空数组按 0 处理。
解法：滚动变量动态规划
核心思路
问题关键：处理当前房屋时只有两种互斥选择：不偷它，沿用前一间为止的最优解；偷它，则只能接在前两间为止的最优解后面。
为什么选动态规划：暴力枚举“偷或不偷”有 $2^n$ 种组合，而每一步真正需要的只有前两个最优值。定义
dp[i]为考虑到第i间房屋时的最大金额，可得dp[i] = max(dp[i-1], dp[i-2] + nums[i])。状态与不变量：遍历当前金额
num前，pre表示再前一间为止的最优值，cur表示前一间为止的最优值。先算next = max(cur, pre + num)，再整体向前滚动；因此每次循环后，cur都是已处理前缀的最优答案。
解题步骤
- 初始化
pre = 0、cur = 0，相当于数组前有两个收益为 0 的空状态。- 对每个
num，比较“不偷当前房屋”的cur与“偷当前房屋”的pre + num。- 用较大值生成
next，再更新pre = cur、cur = next，注意不能提前覆盖旧状态。- 遍历结束返回
cur。例如
[2,7,9,3,1]的cur依次为2、7、11、11、12，最优选择是第 1、3、5 间。
代码实现
class Solution {
public int rob(int[] nums) {
int pre = 0;
int cur = 0;
for (int num : nums) {
int next = Math.max(cur, pre + num);
pre = cur;
cur = next;
}
return cur;
}
}
func rob(nums []int) int {
pre := 0
cur := 0
for _, num := range nums {
next := cur
if pre+num > next {
next = pre + num
}
pre = cur
cur = next
}
return cur
}
复杂度分析
- 时间复杂度：$O(n)$，每间房屋处理一次。
- 空间复杂度：$O(1)$，只保留前两个状态。
关键点总结
- 状态是“考虑到当前位置的最优值”，不是“必须偷当前位置的最优值”。
- 每次都完整比较偷与不偷，局部金额最大不代表全局方案最优。
0, 0初始化让空数组、一间房、两间房自然落入同一套转移。- 环形版本拆成“排除第一间”和“排除最后一间”两次线性 DP，这是常见追问。
易错点总结
- 先更新
pre再计算next：会把pre + num变成前一状态加当前值，相当于允许偷相邻房屋。- 只写
pre + num而不与cur比较：[2,1,1,2]会错过首尾两间组成的最优解 4。- 用“每次选当前较大金额”的贪心：相邻限制会影响后续选择，
[2,7,9,3,1]的最优值 12 无法由局部选择保证。- 手工初始化
nums[0]、nums[1]却不处理短数组：[]或[5]会越界；滚动状态从0,0开始更稳妥。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 213. 打家劫舍 II | 中等 | 环形排列：首尾相邻，拆成两次线性 DP 取较大者 |
| 337. 打家劫舍 III | 中等 | 树形版本：后序遍历，每个节点返回「偷/不偷」两个状态 |
| 740. 删除并获得点数 | 中等 | 数值相邻互斥：按值桶计总点数后转化为线性打家劫舍 |
| LCR 089. 打家劫舍 | 中等 | 与 198 同题，练习滚动变量的标准写法 |
| LCR 090. 打家劫舍 II | 中等 | 与 213 同题，练习环形拆段的完整推导 |
| 面试题 17.16. 按摩师 | 简单 | 同一转移方程的入门包装，适合先手写热身 |