题目描述
一排房子各有现金，不能偷相邻两家(会报警)，求最多能偷到多少。
思路解析
最直接的想法：让每家都「偷 / 不偷」二选一，再扔掉相邻冲突的组合——n 家就有 2 的 n 次方种，组合数指数爆炸。而且「前 i 家最多偷多少」这个小问题，会在不同枚举分支里被反复重算。慢就慢在重复子问题。
换个角度：dp[i] 记「到第 i 家为止最多偷多少」。到第 i 家只有两条路——不偷就继承 dp[i-1]；偷就只能接不相邻的 dp[i-2] 再加 nums[i]。取大的：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。为什么能记表？每个「前 i 家」只算一次存进 dp，后面直接查，省掉重复递归——这就是重叠子问题。
建表：表固定 1 行 5 列，表头是每家的现金。dp[i] 表示「到第 i 家为止最多能偷多少」，咱从左到右一格一格填。
dp[0] = 2 · 地基：只有第 1 家时肯定偷：dp[0] = 2。这是不依赖别人的「地基」格。
dp[1] = max(2, 7)：前两家相邻只能选一个：不偷第 2 家就拿 dp[0]=2，偷第 2 家就拿 7。取大的 7，dp[1] = 7。
dp[2] · 偷 9：看第 3 家：偷它(9)就得跳过相邻的第 2 家，接 dp[0]=2，共 11；不偷就继承 dp[1]=7。偷更赚，dp[2] = 11。这就是核心一步——偷当前要接 dp[i-2]，不是 dp[i-1]。
dp[3] · 先试「偷它」：看第 4 家(3)：先算「偷」这条路——跳过第 3 家、接 dp[1]=7，加上 3 得 10。先记着这个候选，还要和「不偷」比一比。
dp[3] · 偷它不如不偷：再看「不偷」：直接继承 dp[2]=11。偷它(10)反而不如不偷(11)。这一步是负例：偷当前并不总是赚，max 自动选了「不偷、继承 dp[i-1]」。dp[3] = 11。
dp[4] · 偷 1：最后一家(1)：偷它接 dp[2]=11 共 12，比不偷的 11 多 1。dp[4] = 12。
答案 = 最后一格：表格最后一格 dp[4] = 12 就是答案，正对应偷第 1、3、5 家(2+9+1)。每个值只算了一次。
「选当前 + 跳过相邻」和「不选当前 + 继承上一个」取最优——打家劫舍、删除并获得点数、按摩师都是这个套路。
参考代码（Python）
1def rob(self, nums):
2 if not nums: return 0
3 prev2, prev1 = 0, 0 # dp[i-2], dp[i-1]
4 for x in nums:
5 cur = max(prev1, prev2 + x) # 不偷 vs 偷
6 prev2, prev1 = prev1, cur # 滚动前移
7 return prev1复杂度分析
- 时间复杂度：O(n) —— 从头到尾扫一遍，每家只算一次
- 空间复杂度：O(1) —— 只滚动 prev2、prev1 两个变量，不用整张表
套路模板
记住骨架：不选 = 继承 prev1、选 = prev2 + 当前、两者取优、滚动前移。改一下「选的约束」就能套一大类一维 DP。
1# 「每个元素选或不选、选了有约束」都套
2prev2, prev1 = 0, 0
3for x in nums:
4 cur = max(prev1, # 不选当前
5 prev2 + x) # 选当前(接更前面的)
6 prev2, prev1 = prev1, cur
7return prev1易错点
- 错误写法：偷当前时接 dp[i-1] → 正确写法：接 dp[i-2]（相邻不能同偷，偷第 i 家必须跳过紧挨的第 i-1 家，只能接 dp[i-2]）
- 错误写法：滚动赋值顺序写反 → 正确写法：prev2, prev1 = prev1, cur 一次性更新（先改 prev1 再用它算 prev2，会用到被覆盖的旧值导致结果错）
- 错误写法：空数组不特判 → 正确写法：先处理 nums 为空返回 0（否则空输入时返回值含义不对）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。