题目描述
一排房子各有现金，不能偷相邻两家(会报警)，求最多能偷到多少。
nums = [2, 7, 9, 3, 1]
输出 = 12 （偷 2 + 9 + 1）
思路解析
要是挨个枚举每家偷或不偷，再排除相邻冲突，组合数爆炸。其实你只需要想清楚：到每家时，偷它和不偷它哪个赚得多，然后把结果记下来。
到第 i 家，你有两种选择：不偷，那就继承 dp[i-1]；或者偷，那只能接 dp[i-2]，再加上 nums[i]。两者取大的：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
建表：表头是每家的现金。dp[i] 表示「到第 i 家为止最多能偷多少」。
dp[0] = 2：只有一家，那肯定偷：dp[0] = 2。
dp[1] = max(2,7)：两家相邻只能选一个，偷金额大的那个 7：dp[1] = max(2, 7) = 7。
dp[2] · 偷 9：偷第 3 家（9）就得接 dp[0]=2，共 11；不偷的话是 7。取大的，11。
dp[3]：偷第 4 家（3）接 dp[1]=7 共 10，不如不偷的 11。所以 dp[3] = 11。
dp[4] · 偷 1：偷第 5 家（1）接 dp[2]=11 共 12，比 11 大。dp[4] = 12 就是答案。
「选当前 + 跳过相邻」和「不选当前 + 继承上一个」取最优——打家劫舍、删除并获得点数、按摩师都是这个套路。
参考代码（Python）
Python
1if not nums: return 0
2prev2, prev1 = 0, 0 # dp[i-2], dp[i-1]
3for x in nums:
4 cur = max(prev1, prev2 + x) # 不偷 vs 偷
5 prev2, prev1 = prev1, cur # 滚动前移
6return prev1复杂度分析
- 时间复杂度：O(n) —— 扫一遍
- 空间复杂度：O(1) —— 滚动两个变量
套路模板
记住骨架：不选=继承 prev1、选=prev2+当前、两者取优、滚动前移。改一下「选的约束」就能套一大类一维 DP。
Python
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]（相邻不能同偷，要跳过紧挨的那家）
- ❌ 空数组不特判 → ✅ 先处理 nums 为空（否则返回值/下标越界）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。