陷阱三：动态规划——状态定义不完整、状态转移方程错误、边界条件遗漏、维度爆炸

动态规划，简称 DP，是组合优化里的重头戏。

说实话，我见过太多人在 DP 上栽跟头了。我自己也踩过不少坑。今天咱们就聊聊 DP 里最常见的四个误区。

3.1 状态定义不完整

这是最要命的错误。状态定义错了，后面全白搭。

什么叫「不完整」？说白了，就是你定义的状态，没法唯一确定后续的决策。

举个例子：背包问题里，如果你只定义 dp[i] 表示前 i 个物品的最大价值，那你就没法知道当前背包还剩多少容量。这就是状态不完整。

正确的做法是：dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。

我在项目中遇到过一个问题：一个调度系统，状态只记录了当前时间，没记录机器的剩余可用时间。结果算出来的调度方案根本不可行。嗯，那次排查花了我整整两天。

3.2 状态转移方程错误

状态定义对了，转移方程写错，同样白搭。

转移方程的本质是什么？就是「当前状态怎么从之前的状态推出来」。你想想看，如果这个关系搞错了，那结果能对吗？

常见错误：

• 漏掉了某些转移来源
• 转移时用了错误的状态值
• 没有考虑「不选」的情况

比如经典的 0-1 背包：

// 错误写法：漏掉了不选当前物品的情况
dp[i][j] = dp[i-1][j - w[i]] + v[i];

// 正确写法：要考虑选和不选两种可能
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);

我个人习惯在写转移方程之前，先用文字描述一遍：「当前状态可以从哪几个前驱状态得到？」写清楚了再动手编码。

3.3 边界条件遗漏

边界条件，说白了就是「起点」和「终点」怎么处理。

我见过最典型的错误：

• 数组下标越界（访问了 dp[-1] 或 dp[n]）
• 初始值设置不对（比如求最小值时初始化为 0，而不是 INF）
• 漏掉了某些特殊情况的处理

举个例子：爬楼梯问题，dp[0] 应该等于多少？

很多人直接写 dp[0] = 0，然后发现 dp[2] 算出来是 1，但正确答案是 2。为什么？因为 dp[0] 应该等于 1（表示「从第 0 级到第 0 级，有一种方式：不动」）。

3.4 维度爆炸

这是 DP 里最让人头疼的问题。状态定义得太细，维度太多，内存直接爆掉。

你想想看，如果状态有 5 个维度，每个维度取值 100，那就是 100^5 = 100 亿个状态。别说内存了，时间也受不了。

怎么解决？

1. 压缩维度：看看能不能合并某些维度。比如背包问题里，可以用滚动数组把二维压成一维。
2. 状态简化：重新思考，是不是真的需要这么多信息？
3. 换思路：如果 DP 实在不行，考虑贪心、分支定界等其他方法。

我记得有一次做物流路径优化，状态定义到了 4 维，内存直接 16GB 都不够。后来我重新分析了问题，发现有两个维度其实是冗余的，合并后降到 2 维，内存瞬间降到 200MB。

知识体系总览

下面这张图，把 DP 的四个误区串起来了。你可以对照着检查自己的代码。

总结一下

动态规划这四个误区，说白了就是：

• 状态定义：信息要全，不能少
• 转移方程：关系要对，不能错
• 边界条件：起点终点，不能漏
• 维度控制：状态数量，不能多

我个人习惯是，每写一个 DP，都按这个清单过一遍。虽然麻烦点，但能省下后面大量的调试时间。

嗯，今天就聊到这儿。记住，DP 不是玄学，是有章可循的。把上面四个点盯住了，你也能写出优雅的 DP 代码。