LeetCode LCR 089. 打家劫舍
目录
题目描述
题意分析
一排房屋，第
i家藏有nums[i]的现金。规则只有一条：不能偷相邻的两家，否则会触发警报。求在这条约束下能偷到的最大金额。
把题意抽象干净：在数组里挑一个任意两个下标都不相邻的子集，使元素和最大。注意约束是「不相邻」而不是「不连续」——
[0, 2, 4]合法，[0, 1]不合法，中间隔两个以上当然也合法。同时没有任何数量限制，可以一家都不偷（金额 0），也可以隔一家偷一家。
只要最大金额、不要具体方案，说明不必枚举子集，可以逐位递推。而每一位的选择只受紧邻的前一位是否被选的影响——第
i家能不能偷，只取决于第i-1家偷没偷，与更早的家无关。这个「影响范围只有 1」的性质就是无后效性，也是这道题能用一维递推解决的根本原因。
约束：
1 ≤ nums.length ≤ 100，0 ≤ nums[i] ≤ 400。规模极小，所以本题考的完全是状态定义和边界的准确性，不是效率。金额非负这一点保证了「多偷一家不会变亏」，但要注意不能因此就贪心地偷所有能偷的——[2, 7, 9]里贪心先偷 9 或先偷 2 都不是最优解2 + 9 = 11的推理方式。
边界：数组长度可能为 1，此时答案就是唯一那个元素；元素可能为 0，
[0, 0, 0]的答案是 0；答案最大不过 $100 \times 400 / 2$ 量级，int完全够用。
解法：动态规划递推
核心思路
暴力做法是枚举每家偷或不偷的全部 $2^n$ 种组合，逐个检查有没有相邻冲突并求和。瓶颈在于「前
i家的最优收益」这个子问题被无数条前缀重复计算——真正影响后续决策的只有「第i家有没有被偷」，前面具体怎么偷完全不重要。
关键观察是：只要记录「考虑完前
i家所能得到的最大收益」，前面的具体选法就可以彻底丢弃。这一步把指数级的子问题压缩成n + 1个。
定义状态：
f[i]表示只考虑前i家（即nums[0..i-1]）时能偷到的最大金额。这里刻意采用「前i家」而不是「以第i家结尾」的口径，好处是f[i]已经把「第i家偷或不偷」两种情况都取过最大值，答案直接就是f[n]，不需要在最后再扫一遍取 max。
转移方程按「第
i家偷不偷」分类。不偷第i家，收益就是前i-1家的最优解f[i-1]；偷第i家，则第i-1家必须放弃，收益是f[i-2] + nums[i-1]（注意状态下标比数组下标大 1，第i家对应nums[i-1]）。两者取大：
f[i] = max(f[i-1], f[i-2] + nums[i-1])
基准情形：
f[0] = 0，一家都不考虑自然收益为 0；f[1] = nums[0]，只有一家时偷了就是最优（金额非负）。有了这两个基准，i从 2 开始的递推就不会碰到负下标。
这套「选或不选，选了就跳过前一个」的结构，是带间隔约束的最优子集问题的通用模板。
解题步骤
- 开长度为
n + 1的数组：状态用「前i家」口径，下标要从 0 取到n，多出的那一格既是基准也是答案位。这个偏移是本题最容易搞混的地方，写代码前先把「f[i]对应nums[i-1]」这句话记牢。
- 写死两个基准：
f[0] = 0由默认零值给出；f[1] = nums[0]必须显式赋值。f[1]不能想当然写成 0——只有一家时当然要偷。
- 从
i = 2正序递推到n：f[i]依赖f[i-1]与f[i-2]，都是更小的下标，因此正序即可保证被依赖的值已经算好。起点是 2，因为 0 和 1 是基准。
- 转移取两分支最大值：
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1])。左分支是「不偷第i家」，右分支是「偷第i家并跳过第i-1家」。右分支里必须是f[i-2]而不是f[i-1]，否则就允许了相邻同偷。
- 返回
f[n]：因为状态定义已经包含了「第n家偷或不偷」两种情况，直接返回，不需要max(f[n], f[n-1])。
以
nums = [2, 7, 9, 3, 1]走一遍，n = 5，f长度为 6。
基准：
f[0] = 0（不考虑任何一家），f[1] = nums[0] = 2（只有第一家，偷它）。
i = 2（对应nums[1] = 7）：不偷得f[1] = 2；偷则跳过第 1 家，得f[0] + 7 = 7。取大，f[2] = 7。
i = 3（对应nums[2] = 9）：不偷得f[2] = 7；偷则跳过第 2 家，得f[1] + 9 = 2 + 9 = 11。取大，f[3] = 11，对应偷第 1、3 家。
i = 4（对应nums[3] = 3）：不偷得f[3] = 11；偷则得f[2] + 3 = 7 + 3 = 10。取大，f[4] = 11——这一步的意义是「第 4 家不值得偷」，最优解保持不变。
i = 5（对应nums[4] = 1）：不偷得f[4] = 11；偷则跳过第 4 家，得f[3] + 1 = 11 + 1 = 12。取大，f[5] = 12，对应偷第 1、3、5 家，金额2 + 9 + 1 = 12。
返回
f[5] = 12。注意i = 4那一步：即使当时选择了「不偷」，f[4]里保存的最优方案（偷第 1、3 家）恰好为下一步腾出了空间，这正是「只保留最优值、丢弃具体方案」仍然正确的体现。若把右分支误写成f[i-1] + nums[i-1]，i = 3会算出7 + 9 = 16，等于同时偷了相邻的第 2、3 家，答案膨胀成非法值。
代码实现
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// f[i]：只考虑前 i 家能偷到的最大金额；第 i 家对应 nums[i - 1]。
int[] f = new int[n + 1];
// f[0] = 0 由默认零值给出；只有一家时必偷。
f[1] = nums[0];
for (int i = 2; i <= n; ++i) {
// 左：不偷第 i 家；右：偷第 i 家，必须跳过第 i - 1 家。
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
}
return f[n];
}
}
func rob(nums []int) int {
n := len(nums)
// f[i]：只考虑前 i 家能偷到的最大金额；第 i 家对应 nums[i-1]。
f := make([]int, n+1)
// f[0] = 0 由默认零值给出；只有一家时必偷。
f[1] = nums[0]
for i := 2; i <= n; i++ {
// 左：不偷第 i 家；右：偷第 i 家，必须跳过第 i-1 家。
f[i] = max(f[i-1], f[i-2]+nums[i-1])
}
return f[n]
}
复杂度分析
- 时间复杂度：$O(n)$，从 2 扫到
n一趟，每格一次加法一次比较，都是常数操作。- 空间复杂度：$O(n)$，用了长度为
n + 1的数组。由于f[i]只回看两格，可以用两个变量滚动降到 $O(1)$；面试中写完完整数组版后主动补一句「可以压成常数空间」通常是加分项，而下一题「打家劫舍 II」正是用滚动写法的。
关键点总结
- 「选或不选」是最优子集类 DP 的通用切入点：对第
i个元素分两种情况讨论，不选则继承f[i-1]，选则跳到约束允许的最近位置f[i-2]再加上自身价值。间隔约束改成k时，右分支就换成f[i-k-1]，模板可以直接迁移。- 状态定义用「前
i个」而非「以第i个结尾」，可以省掉最后的取最大值。两种口径都对，但要一开始就选定并贯彻，中途混用是这类题最常见的出错方式。- 状态下标与数组下标的偏移必须写在纸上：本题
f[i]对应nums[i-1]。凡是多开一格作为基准的 DP，都要显式确认这个映射，转移里写错一个下标就全盘皆输。- 无后效性来自「影响范围只有相邻一格」：识别出这一点，就知道不需要记录前面偷了哪些家，只需一个数值。这是从暴力枚举跳到 DP 的核心推理，面试时要讲出来。
- 不要试图用贪心：「先偷最大的再排除相邻」在
[2, 7, 9, 3, 1]上会先选 9、排除 7 和 3，再选 2 和 1 得 12，恰好正确，但在[2, 1, 1, 2]上会先选某个 2、排除相邻的 1，再选另一个 2 得 4，虽然也对，可一旦价值分布稍复杂（如[4, 5, 4]中先选 5 得 5，最优却是4 + 4 = 8）贪心立刻失效。
易错点总结
- 右分支写成
f[i-1] + nums[i-1]：nums = [2,7,9]会算出f[3] = 2 + 7 + 9 = 18，等于把相邻三家全偷了，明显违规。- 忘记
f[1] = nums[0]：nums = [5]直接返回f[1] = 0，而正确答案是 5。- 数组开成
new int[n]：nums = [2,7]时循环写到i = n就越界。- 转移里写成
nums[i]而不是nums[i-1]：i = n时越界；即使不越界，nums = [2,7,9]也会整体错位，算出把第 2、3 家当成第 1、2 家的错误结果。- 循环从
i = 1开始：会访问f[-1]，直接越界。- 返回
max(f[n], f[n-1])：结果虽然仍对（f[n] ≥ f[n-1]恒成立），但说明没理解「前i家」的定义已经含了取最大，面试中会被追问到答不上来。- 改用「以第
i家结尾」的定义却仍返回f[n]：nums = [2,7,9,3,1]会返回「必须偷第 5 家」的 12，看似正确，但在nums = [2,7,9,3]上会返回f[4] = 10而不是 11，因为漏掉了「不偷最后一家」的情况。- 误以为答案一定包含最大元素：
nums = [4,5,4]时最大元素是 5，但最优解是4 + 4 = 8，说明局部最大不等于全局最优，任何贪心选法都不成立。- 滚动数组优化时先更新
pre再更新cur：nums = [2,7,9]第二轮会用到已被覆盖的值，算出 9 而不是 11，必须借助临时变量或同时赋值。- 把「不能相邻」误读成「不能连续偷两次以上」：
nums = [1,1,1,1]会允许偷第 1、2 家，答案变成 3 而不是正确的 2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 与本题完全同题，代码可原样提交 |
| 213. 打家劫舍 II | 中等 | 房屋成环，首尾互斥，需拆成两段线性区间各跑一次再取大 |
| LCR 090. 打家劫舍 II | 中等 | 与 213 同题，是本题在环形结构上的直接升级 |
| 337. 打家劫舍 III | 中等 | 房屋排成二叉树，改为树形 DP，每个节点返回「偷/不偷」两个值 |
| 740. 删除并获得点数 | 中等 | 先按数值桶排序转成价值数组，再套本题模板，考察问题转化能力 |
| 面试题 17.16. 按摩师 | 简单 | 与本题同构的另一处收录，可用来练滚动变量写法 |
| 746. 使用最小花费爬楼梯 | 简单 | 同为一维线性 DP，约束从「不相邻」换成「步长 1 或 2」，取 min 而非 max |
| 918. 环形子数组的最大和 | 中等 | 同为环形上的最优子结构，用「总和减最小子数组」把环拆成线性 |