用不变量理解动态规划

状态：复习中。这篇是我重学 DP 时的整理稿，例子和表述还在打磨；发现问题欢迎评论区指出。

1. 问题描述

动态规划题最让人挫败的不是「想不出转移」，而是看题解能懂、自己写就错。我把这种错拆解后发现，几乎都不是转移方程的问题，而是状态定义、初始化、遍历顺序三者没有对齐。

这篇手记把「状态定义」当作 DP 里的不变量来对待，用一个贯穿的例子说明：定义写清楚了，其余部分几乎是被推出来的。

2. 直觉与观察

DP 的标准教法是「设计状态 → 写转移方程 → 确定初始化和顺序」。但三个步骤里，只有第一步是决策，后两步是推论——前提是状态定义足够精确。

「精确」的标准：把定义念出来，任何一个下标组合的含义都必须无歧义、可判定。

以爬楼梯（LeetCode 70）为例，两种写法的差别：

• 模糊版：「dp[i] 表示到第 i 阶的方案数」——「到」是什么意思？最后一步跨了几阶？
• 精确版：「dp[i] 表示恰好站在第 i 阶台阶上的方案数」——那么 $dp[i] = dp[i-1] + dp[i-2]$，含义清楚：最后一步要么从 i-1 跨 1 阶，要么从 i-2 跨 2 阶。

3. 推导过程：一个贯穿的例子

打家劫舍（LeetCode 198）：沿街房屋存放着金额 nums[i]，不能偷相邻两间，求最大金额。

第一步：写状态定义，带限定词。

第二步：转移是被推出来的。

• 第 $i$ 间不偷：前一间可偷可不偷，$dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1])$；
• 第 $i$ 间偷：前一间必须不偷，$dp[i][1] = dp[i-1][0] + nums[i]$。

注意第二行为什么不是 $\max(dp[i-1][0], dp[i-1][1]) + nums[i]$——因为「偷 $i$」这个事实约束了 $i-1$ 的取值。约束从哪来？从状态定义里「且第 $i$ 间偷」这半句来。定义即判据。

第三步：初始化同样被推出来。

$dp[0][0] = 0$（没有房子，不偷，金额为 0）；$dp[0][1]$ 是非法状态（不存在「偷第 0 间又不偷第 0 间」）——用 $-\infty$ 屏蔽，或直接从 $i = 1$ 开始按含义填。答案取 $\max(dp[n][0], dp[n][1])$。

对比常见的「一维版」$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$：它把「偷/不偷」压进 max 里，短，但复查时你要在脑子里重新展开成二维含义。短模板是熟练后的压缩，不是学习的起点。

4. 三者对齐的检查清单

把状态定义当不变量，写完 DP 后按这三问复查：

1. 初始化符合定义吗？ 每个 $dp[\cdot]$ 的初值，按定义念一遍是否为真（尤其是 $i = 0$ 的边界和「非法状态」的处理）；
2. 每条转移都保住定义吗？ 转移右侧用到的状态，其「限定条件」是否允许被左侧状态继承（像 $dp[i][1] \leftarrow dp[i-1][0]$ 这样，约束要连贯）；
3. 遍历顺序是定义的拓扑序吗？ 计算 $dp[i]$ 时它依赖的所有状态必须已算好——背包问题的「0-1 倒序、完全正序」本质就是这条检查的结论，而不是需要单独背的规则。

5. 复杂度与边界

• 状态数 $O(n)$（或 $O(n \cdot k)$，带附加维度时）× 单状态转移 $O(1)$（本题）；
• 空间：滚动数组可把二维压到 $O(1)$（只依赖 $i-1$）；
• 边界：nums 为空 → 答案 0；单间房 → max(0, nums[0])——都从定义直接读出。

6. 常见错误（复习中持续补充）

1. 状态定义省略限定词，转移「看起来对」，边界输入就翻车；
2. 非法状态初始化成 0 而不是 $-\infty$，让非法路径混进答案；
3. 0-1 背包容量枚举写成正序，物品被重复选取；
4. 答案取错位置：取 $dp[n]$ 还是 $\max(dp[n][0], dp[n][1])$，取决于定义里是否压缩了决策维度。

7. 相关练习

• LeetCode 198 / 213 · 打家劫舍 I/II（环形约束如何改定义）；
• LeetCode 322 · 零钱兑换（「恰好装满」初始化）；
• LeetCode 1143 · 最长公共子序列（二维下标 + 限定词练习）。

下一篇建议读 045《Dijkstra 为什么要求非负权边》——贪心的正确性同样可以找到一句不变量。