打家劫舍：每一间房，只做一次选择
贪心「见钱就拿」会踩中相邻报警器。真正可靠的办法是让每间房比较两种未来：偷它（接上上家）还是不偷（保持上家）。
对每间房 i，dp[i] = max(dp[i-1], dp[i-2] + nums[i])：不偷它则收益沿用上一间的最优，偷它则必须跳过相邻的 i-1、接上 i-2 的最优。dp[i] 只依赖前两个值，所以用 prev2、prev1 两个滚动变量即可。时间 O(n)，空间 O(1)。
一排房子，每间藏着一定金额的现金。相邻两间装了联动报警器：一旦同时被偷就会触发。问：在不偷相邻两间的前提下，最多能偷到多少？
这个限制不是刁难——它正是把「任意子集」压缩成「每隔一间选一次」的那把锁。
这篇文章从一个注定失败的贪心直觉讲起，再用一间一间房的二元决策推导出递推式，最后落到两行滚动赋值。读完后你会明白：DP 的「状态」不是玄学，而是「我已经把前 i 家处理好了，现在只需要决定第 i+1 家怎么选」。
先看清约束在说什么
输入 nums = [2, 7, 9, 3, 1]，每间房可以偷或跳过，但不能同时偷相邻两间。
先试几个直觉答案：偷 2 + 9 + 1 = 12？可行，因为下标 0、2、4 互不相邻。偷 7 + 9 = 16？不行，7 和 9 相邻。
所以问题不是「尽量多偷」，而是「在不相邻约束下选一个子集，使总和最大」。
注意这个约束带来的第一句话：一旦决定了第 i 间房偷不偷，它只会影响相邻的两间，离它远的选择完全不受影响——这意味着问题天然具有「局部决策、全局最优」的结构。
贪心直觉：见钱就拿，为什么失败
新手的第一反应往往是贪心：从左到右，能偷就偷，偷完一间跳到下一间。
拿 nums = [2, 1, 1, 2] 试试。贪心先偷下标 0 的 2，下标 1 被锁死跳过，下标 2 又能偷（1），下标 3 被锁死跳过——总额 2 + 1 = 3。看似不错，但最优解是偷下标 0 的 2 和下标 3 的 2，共 4。
贪心输在哪？它「见钱就拿」地抢了下标 2 的 1，结果把最后一间更值钱的 2 锁死在外面。局部的「现在能偷」不等于全局最优——每一步贪心，都会付出看不见的未来代价。
再看 [3, 2, 2, 3]：贪心偷 0 和 2，得 5；最优却是偷 0 和 3，得 6。同样的短视。这两组数据都证明：靠直觉选子集不可靠，必须让每间房预知两种未来再做决定。
反例贪心的失败在于它只看眼前：偷了第一间，就失去了未来更值钱的两端组合。DP 正是用来纠正这种短视的。
把未来翻译成状态：dp[i] 是什么
既然贪心不行，就要让每间房都能「预知两种未来」再做决定。先定义一个明确的状态：
dp[i] = 只考虑前 i+1 间房（下标 0..i）时，能偷到的最大金额。答案就是 dp[n−1]。
为什么这个状态足够？因为第 i 间房的决定只依赖「i−1 之前已经处理完」的结果——房子们从左到右天然有序，任何局部决策都不会影响已经过去的房子。
再定义两种转移：不偷第 i 间，那么前 i+1 间的最大收益就是前 i 间的最大收益 dp[i−1]；偷第 i 间，则第 i−1 间不能偷，收益 = 前 i−1 间的最大收益 dp[i−2] 加上 nums[i]。
状态语义dp[i] 不记录「最后一间偷没偷」，只记录「前 i+1 间的最优总额」——信息被刻意压缩，只留下决策需要的部分。
逐间推进：cur = max(prev1, prev2 + nums[i])
完整地走一遍示例 nums = [2, 7, 9, 3, 1]。初始化时还没有任何房子，记 prev2 = 0（dp[-2]）、prev1 = 0（dp[-1]）。
i = 0，nums[0] = 2：不偷得 0，偷得 0 + 2 = 2，取大 cur = 2。滚动：prev2 ← 0，prev1 ← 2。
i = 1，nums[1] = 7：不偷得 2，偷得 0 + 7 = 7，取大 cur = 7。滚动：prev2 ← 2，prev1 ← 7。
i = 2，nums[2] = 9：不偷得 7，偷得 2 + 9 = 11，取大 cur = 11。滚动：prev2 ← 7，prev1 ← 11。
i = 3，nums[3] = 3：不偷得 11，偷得 7 + 3 = 10，取大 cur = 11。滚动：prev2 ← 11，prev1 ← 11。
i = 4，nums[4] = 1：不偷得 11，偷得 11 + 1 = 12，取大 cur = 12。答案 12：偷下标 0、2、4 三间。
为什么两个变量就够
看递推式 dp[i] = max(dp[i−1], dp[i−2] + nums[i])：计算 dp[i] 只需要 dp[i−1] 和 dp[i−2] 两个历史值，更早的值再也不会被用到。
于是整张 dp 表可以压缩成两个滚动变量：cur 是「处理完当前房」的最优，prev1 是「上一间」的最优，prev2 是「上上间」的最优。每次迭代：prev2 ← prev1，prev1 ← cur。
空间从 O(n) 降到 O(1)，时间保持 O(n)——每一个房子仍然只做一次常数时间的决策。
这种「只保留最近 K 个状态」的压缩在 DP 里随处可见，比如 LC70 爬楼梯、LC746 最小花费爬楼梯，都是同一种滚动写法。
滚动变量依赖窗口只有 2 个历史值，数组就可以换成两个变量——这是把「状态依赖」读进复杂度里。
易错点与变式
第一个易错点：忘记处理空数组。nums 为空时答案应是 0，dp[-1]、dp[-2] 都取 0 天然正确，但代码里要保证不越界访问 nums[0]。
第二个易错点：把递推写成 dp[i] = max(dp[i−1], dp[i−2]) + nums[i]，这会同时偷了相邻两间——错误。加 nums[i] 只发生在「偷第 i 间」这个分支里。
LC213 是环形变体：首尾相邻。解法是跑两次线性 DP——一次不偷第 0 间，一次不偷最后一间，取较大者。
LC337 是树形变体：改成在二叉树上相邻父子不能同时偷。状态升级成「每棵子树两种选择」的两个返回值，但决策逻辑一脉相承。
面试表达先讲反例打破贪心，再定义 dp[i] 的语义，最后推导两种转移——面试官会看到你真的懂 DP 而不是背模板。
Go：滚动两个变量
func rob(nums []int) int {prev2, prev1 := 0, 0for i := 0; i < len(nums); i++ {// 不偷 i → prev1；偷 i → prev2 + nums[i]cur := max(prev1, prev2+nums[i])prev2 = prev1prev1 = cur}return prev1}func max(a, b int) int { if a > b { return a }; return b }
1prev2 是 dp[i-2]，prev1 是 dp[i-1]，初始都是 0（空数组答案）。
2每间房只做一次决策。
3不偷沿用 prev1，偷则接 prev2 加当前值。
4取大者作为本房最优。
5滚动：prev2 ← prev1，prev1 ← cur。
6处理完所有房，prev1 即答案。
总结
每间房比较「偷（接上上家）」与「不偷（保持上家）」，滚动两个变量。
- 贪心失败在于短视：偷了眼前，失去未来两端的组合。
- dp[i] 语义：前 i+1 间房的最优总额；转移只依赖 dp[i-1] 与 dp[i-2]。
- 两个滚动变量代替整张表：时间 O(n)、空间 O(1)。
- LC213 环形、LC337 树形都从这个二元决策长出。