动态规划专题

我曾经把“动态规划专题”学成了一组互不相干的名词和代码。具体表现是：动态规划曾经是我最抗拒的一部分，答案里的状态转移看起来很自然，轮到自己就连 dp 数组表示什么都定不下来。后来我尝试只保留一个问题：它到底在减少哪一种重复工作？顺着这个问题，整块知识才稳定下来。

动态规划专题是算法篇里最需要慢慢打磨的一章。DP 难的不是代码，而是把一个问题拆成状态、选择、转移、初始化和遍历顺序。

我的建议是：不要一上来追求做难题，先把几类核心模型吃透。只要能把状态定义说清楚，很多 DP 题就会从“玄学”变成“工程建模”。

为什么会需要动态规划

递归计算斐波那契数时，f(5) 会计算 f(4) 和 f(3)，而 f(4) 内部又会再次计算 f(3)。同一个子问题被反复求解，规模稍大就会指数膨胀。把已经得到的 f(3) 保存下来，下次直接复用，就是动态规划最朴素的起点。

第一次学习只做三件事：用一句话定义状态，写出当前状态依赖谁，确定依赖项应当先于谁计算。空间压缩和复杂变体可以放到第二遍。

我为什么先补这一章

这一章重点解决：

1. 如何定义状态。
2. 如何找到状态转移。
3. 如何确定遍历顺序。
4. 如何区分线性 DP、背包 DP、区间 DP、树形 DP、数位 DP。

我自己的学习顺序

1. 动态规划：从状态定义到状态转移。
2. 线性 DP 与子序列 DP。
3. 背包 DP。
4. 区间 DP 与状态压缩。
5. 树形 DP。
6. 数位 DP。

我当时最容易混淆的地方

DP 和递归、回溯不是割裂的。很多 DP 本质上是“递归搜索 + 记忆化 + 状态复用”。

背包 DP 最容易错的是遍历顺序。0-1 背包通常容量倒序，完全背包通常容量正序，因为它们对“同一个物品能不能重复使用”的要求不同。

区间 DP 的关键是先枚举区间长度，再枚举左右边界，否则依赖关系可能还没算出来。

我后来这样检查自己是否真的理解

• 状态定义为什么比转移方程更重要？
• dp[i] 和 dp[i][j] 分别适合什么问题？
• 为什么树形 DP 通常用后序遍历？
• 数位 DP 里的 tight 解决什么问题？