动态规划经典模型：从状态、决策到三类 DP 模型
动态规划经常被讲成一堆题型：背包、区间 DP、树形 DP、数位 DP、插头 DP、最短路、状态压缩……但如果只记题型，很容易出现一个问题：看到新题时，不知道它到底应该归到哪一类，也不知道状态为什么要这么设计。
更好的理解方式是：动态规划不是先背转移方程，而是先把问题拆成一系列具有相同后效性的子问题。只要能把大量具体决策前缀合并成有限个“状态”，并且这些状态对后续决策的影响相同，就可以用动态规划来减少枚举量。
本文按 slide 的思路，把动态规划整理成三个经典模型：
- 固定多阶段决策类动态规划；
- 路径规划类动态规划；
- 扩展边界类动态规划。
这三类模型并不是互斥的“标签”，而是三种理解 DP 的视角。它们分别回答了三个问题：阶段怎么推进、路径怎么延伸、边界怎么扩张。
1. 动态规划到底在做什么
动态规划常用于组合优化问题和计数问题。它的核心思想是：
将原问题拆成若干子问题，并且每个子问题都能用几个更简单子问题的解快速得到。
这句话和分治、递推、递归很像，但动态规划的关键不只是“拆”，而是合并重复的子问题。
一个暴力搜索会枚举很多具体的决策过程，例如：
- 第一步怎么选；
- 第二步怎么选；
- 第三步怎么选；
- 当前已经形成了什么局面；
- 后面还能怎么走。
动态规划做的是：如果若干个决策前缀对后续的影响完全一样，就把它们归并到同一个状态里。之后不再关心它们具体是怎么来的，只关心这个状态对应的最优值、方案数或可行性。
所以，DP 的本质可以简化为四件事：
- 定义阶段：问题推进到哪里了；
- 定义状态：当前需要保留什么信息，才能决定后面怎么做；
- 设计决策：从当前状态可以做哪些选择；
- 合并影响：把后效性相同的决策前缀合并起来。
2. 固定多阶段决策类动态规划
第一类是最直观的动态规划：固定多阶段决策类 DP。
这类问题有明确的阶段特征。每个阶段都要做一次或若干次决策，当前阶段的状态和当前决策共同决定下一阶段会进入什么状态。
可以抽象成下面这个过程：
阶段 i 的状态
+ 当前阶段的决策
-> 阶段 i + 1 的状态
这种模型的核心是：
- 每种前
i个阶段的有效决策前缀，都被包含在阶段i的某个状态中； - 同一个状态中的所有决策前缀，对后续决策的影响相同；
- 因此可以从“枚举每一种决策前缀”变成“枚举每一种状态和下一步决策”。
这类 DP 的典型例子包括组合数计算、0/1 背包、数位 DP 等。
3. 例一：组合数计算
问题是：有 n 个可区分的球，现在要从中拿出 m 个，问一共有多少种拿法。
我们可以把所有球排成一列，然后从左到右依次经过每个球。每碰到一个球，就必须做一个决策：
- 拿这个球；
- 不拿这个球。
这里的阶段就是“已经处理到第几个球”，状态就是“目前已经拿了几个球”。
设：
表示在前 i 个球中，恰好取出 j 个球的方案数。
从后向性思考看，如果当前已经处理完前 i 个球，并且取了 j 个，那么处理第 i + 1 个球时有两种选择：
- 拿第
i + 1个球：进入状态(i + 1, j + 1)； - 不拿第
i + 1个球：进入状态(i + 1, j)。
所以可以写成类似下面的转移：
for j = 0 ... n:
F[i + 1][j] = 0
for j = 0 ... i:
F[i + 1][j + 1] += F[i][j]
F[i + 1][j] += F[i][j]
从前向性思考看，如果要求 F[i][j]，也可以反过来问：最后一个决策，也就是第 i 个球，有没有被拿？
- 如果拿了第
i个球，那么前i - 1个球中必须拿了j - 1个； - 如果没拿第
i个球，那么前i - 1个球中必须拿了j个。
因此有：
这其实就是组合数递推式。它的重点不在公式本身，而在于公式背后的状态压缩：我们不再记录“具体拿了哪些球”，只记录“处理到第几个球”和“已经拿了几个球”。
4. 后向性思考与前向性思考
动态规划转移可以有两种思考方式。
第一种是后向性思考：
从一个已知状态出发，枚举所有可能的下一步决策，然后把影响传递给后继状态。
这类写法通常像“从当前状态往外扩展”。例如组合数里，从 F[i][j] 转移到 F[i + 1][j] 和 F[i + 1][j + 1]。
第二种是前向性思考：
目标是求解某个状态，考虑它可能由哪些上一个状态和上一个决策转移而来。
这类写法通常像“计算当前状态时向前追溯”。例如组合数里：
多数情况下，这两种思路的难点是一样的。真正关键的是要想清楚：
- 状态里到底需要保存哪些信息；
- 哪些历史信息可以被合并；
- 哪些历史信息会影响后续决策，不能丢掉。
5. 例二：0/1 背包问题
0/1 背包是固定多阶段决策类 DP 的经典模型。
问题是：有 n 个物品，第 i 个物品的重量是 w_i，价值是 v_i。现在背包容量是 W，每个物品最多只能拿一次，问总重量不超过 W 的前提下，最大总价值是多少。
同样可以把物品排成一列，从左到右依次处理。每处理一个物品，就做一次决策：
- 拿这个物品；
- 不拿这个物品。
这里的阶段是“处理到第几个物品”，状态是“当前总重量是多少”。
设：
表示在前 i 个物品中，取出总重量恰好为 j 时能得到的最大价值。
处理第 i + 1 个物品时：
- 如果拿它，那么重量从
j变成j + w_{i+1}，价值增加v_{i+1}； - 如果不拿它，那么重量仍然是
j，价值不变。
对应转移可以写成：
不拿第 i + 1 个物品：
F[i + 1][j] = max(F[i + 1][j], F[i][j])
拿第 i + 1 个物品：
F[i + 1][j + w[i + 1]] = max(
F[i + 1][j + w[i + 1]],
F[i][j] + v[i + 1]
)
时间复杂度是：
这里有一个很容易被忽略的教学问题：常见背包讲解通常会直接把状态定义成“前 i 个物品中，总重量不超过 j 的最大价值”，然后再进一步压缩成一维滚动数组，并且用倒序更新。这种写法很简洁，但它把状态定义、阶段压缩、实现技巧混在了一起。
对于初学者，更建议先从二维状态理解：
阶段：处理到第几个物品
状态：当前总重量是多少
决策：拿或不拿
理解这个模型之后，再去看滚动数组和倒序更新，才不会只是在背模板。
6. 固定多阶段决策类 DP 的常见题型
这一类 DP 的核心特征是：阶段顺序明确，每个阶段都要做决策。
常见题型包括：
- 背包问题：顺序决策每种物品是否选择、选择多少；
- 数位 DP：模拟加法电路，顺序处理每一位数字上的决策；
- 一些带有明确时间、位置、物品序列、字符序列的 DP。
可以用一个检查问题来判断它是不是这一类：
我能不能把问题拆成“处理第 1 个对象、处理第 2 个对象、……、处理第 n 个对象”？
如果可以，并且每一步的历史影响能被有限状态表示，那么它大概率就是固定多阶段决策类 DP。
7. 路径规划类动态规划
第二类是路径规划类动态规划。
它常见于图论中的路径问题。典型算法包括：
- Bellman-Ford；
- Floyd-Warshall；
- Dijkstra；
- DAG 最短路。
和固定多阶段决策类不同，路径规划类问题的阶段划分往往不那么明显：路径长度可能不固定，走到哪里也不完全按线性顺序推进。
但它有一个非常重要的共同点：
对后续影响最关键的信息，通常是当前所在的位置。
也就是说，路径怎么走到当前点，很多时候不重要；重要的是当前到达了哪个点，以及到达这里的最优代价是多少。
8. 例一：Bellman-Ford 算法
问题是：给定一张有向带权图，边权可以为负，但保证没有负环，求源点 s 到所有可达点的最短路径长度。
由于没有负环，最短路径可以看作简单路径，因此可以用“边数”来离散化阶段。
设：
表示从源点 s 到点 v，使用边数不超过 i 时的最短路径长度。如果不存在这样的路径，则记为 +∞。
如果要求使用边数不超过 i + 1 到达 v 的最短路，可以枚举最后一条边 (u, v)。于是得到：
这里的含义是：
- 可以不增加新边，直接沿用
F[i][v]； - 也可以先用不超过
i条边到达某个u，再走一条边到v。
加上滚动数组优化后，就是常见的 Bellman-Ford 算法形式。
9. 例二：Floyd-Warshall 算法
Floyd-Warshall 用来求任意点对之间的最短路径。
它的离散化方式很特别：不是按路径长度分阶段，而是按“允许经过哪些中间点”分阶段。
设：
表示从 i 到 j，中间经过的所有点都在集合 {1, 2, ..., k} 内时的最短路径长度。
当加入第 k + 1 个点作为可选中转点时，有两种情况：
- 最短路不经过
k + 1，那么答案还是F[k][i][j]； - 最短路经过
k + 1，那么可以拆成i -> k + 1和k + 1 -> j两段。
因此：
去掉第一维的滚动数组之后，就得到常见的 Floyd-Warshall 写法：
for k = 1 ... n:
for i = 1 ... n:
for j = 1 ... n:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
这说明 Floyd-Warshall 也是动态规划，只是它的“阶段”不是处理第几个物品，而是允许使用的中间点范围。
10. 例三：DAG 最短路与一维跳跃问题
路径规划类 DP 还有一个常见形态：DAG 最短路。
问题可以表述为：给定一张带边权的有向无环图，求从起点 s 到终点 t 的最短路径长度。
它也可以转化成一维连续跳跃问题：从位置 i 跳到后面的某个位置 j 需要付出代价 w(i, j)，求从 1 跳到 n 的最小代价。
设：
表示从 1 跳到 j 的最小代价。
那么可以枚举上一步的位置 i：
如果把每个位置看成一个点，把能从 i 跳到 j 看成一条边，那么这个问题就是 DAG 最短路。反过来，DAG 最短路也可以看成一类路径规划 DP。
如果 w(i, j) 不是任意的，而是有特殊性质，就可以进一步优化。例如：
- 如果只有存在边时
w(i, j)才有限，那么总转移可以压缩到O(m)； - 如果代价函数满足某些单调性或四边形不等式，就可能使用决策单调性优化。
11. 路径规划类 DP 的常见题型
路径规划类 DP 的核心特征是：状态常常和当前位置有关，转移常常像在图上走边。
常见题型包括：
- 图上的最短路、最长路、路径计数；
- 竞赛中的许多
1D/1D动态规划； - 编辑距离、字符串路径匹配类问题；
- 图计数问题，如有标号树、仙人掌、连通图、有向无环图、二分图、欧拉图计数等。
判断时可以问自己：
这个 DP 的状态和转移，能不能看成图上的点和边？
如果可以，那么它很可能能用路径规划类 DP 的视角来理解。
12. 扩展边界类动态规划
第三类是扩展边界类动态规划。
这一类问题通常具有图状结构，并且存在一系列较小的割集，也可以理解为问题的“边界”比较小。
这类 DP 的核心思想是：
子问题通常是一系列连通子图，后效性只和子图边界处的状态有关。
和前两类不同，固定多阶段决策类、路径规划类通常只需要考虑一个状态怎么转移到下一个状态；而扩展边界类 DP 往往需要综合多个子问题的信息，才能合并成更大的子问题。
它的关键是：
- 图很大，但边界比较小；
- 边界上的状态种类有限；
- 因此可以把后效性编码到边界状态中。
典型题型包括：
- 树形 DP；
- 区间 DP；
- 插头 DP；
- 一些树宽较小的图上 DP。
13. 例一：树上最大权独立集
问题是：给定一棵树，每个节点有权值，求最大权独立集。
独立集的意思是：选出的点之间不能有边相连。
对于树上的任意节点 u，我们讨论它是否被选：
- 如果不选
u，那么它的每个子节点都可以选，也可以不选； - 如果选
u，那么它的所有子节点都不能选。
这说明，对于以 u 为根的子树来说，后续影响只和一个边界状态有关：u 是否被选。
取任意点为根，设：
表示在以 u 为根的子树中，不选 u 时的最大权独立集权值；
表示在以 u 为根的子树中，选 u 时的最大权独立集权值。
如果不选 u，每个子节点 v 都可以自由选择选或不选：
如果选 u，每个子节点 v 都不能选：
树形 DP 的关键不是“树上递归”这么简单，而是树的子问题之间天然被边界节点隔开。只要记录边界节点的状态，就可以把各个子树的答案合并起来。
14. 例二：合并石子问题
问题是：有 n 堆石子，第 i 堆有 a_i 个。每次可以选择相邻的两堆合并，代价是两堆石子的总数。问把所有石子合并成一堆的最小总代价。
在任意时刻，每一堆石子都一定对应原序列中的一个连续区间。例如，某一堆可能由最初的第 i 堆到第 j 堆合并而来。
因此可以定义区间状态：
表示将第 i 堆到第 j 堆合并成一堆的最小代价。
如果最后一步把区间 [i, j] 合并起来，那么在最后一步之前，它一定被分成了两个相邻区间：
[i, k]；[k + 1, j]。
于是有：
其中：
F[i][k]是左区间合并成本；F[k + 1][j]是右区间合并成本；sum(a_l)是最后一次把两堆合并起来的成本。
这个问题就是典型的区间 DP。它的边界是区间的左右端点，子问题由连续区间刻画。
15. 例三：插头 DP 与网格图最长简单路径
扩展边界类 DP 中还有一种更复杂的类型：插头 DP。
一个典型问题是：给定一个带边权的 c × n 网格图，求最长简单路径长度，其中 c ≤ 8，n 很大。
由于网格的一边很窄，另一边很长，可以按某种顺序逐格处理图中的点，例如从左到右、从上到下编号。处理过程中，只维护当前边界附近的信息。
边界处需要记录的信息包括：
- 哪些点已经在路径上；
- 边界上的点之间属于怎样的连通关系；
- 每一段路径的端点在哪里；
- 新加入当前点时，向左、向上的边是否加入路径。
因为 c 很小，所以边界大小有限，合法状态数量也有限。每次处理新点时，只需要更新边界上的连通关系。
这类在边界上维护连通性、要求路径像“插头”一样前后对齐的动态规划，常被称作插头 DP。它通常还需要配合状态编码与解码技巧。
16. 扩展边界类 DP 的常见题型
这一类 DP 的重点是：用小边界表示大图中的后效性。
常见类型包括：
| 类型 | 子问题如何刻画 | 状态规模特点 |
|---|---|---|
| 区间 DP | 用连续子区间 [l, r] 刻画 | 通常有 O(n^2) 个区间 |
| 树形 DP | 用真子树刻画 | 通常有 O(n) 个子树 |
| 插头 DP | 用一系列小割集刻画边界 | 边界上常有指数级状态 |
如果问题有明显的图结构，并且某种处理顺序下“已处理部分”和“未处理部分”之间的边界很小，那么就可以尝试扩展边界类 DP。
17. 动态规划优化：不要只当成模板背
动态规划有很多优化技巧，但这些优化通常不是凭空出现的。很多时候，一个 DP 优化本质上是在求解另一个经典数据结构或算法问题。
可以这样理解：
| DP 场景 | 常见优化 | 背后对应的问题 |
|---|---|---|
| 一般动态规划问题 | 滚动数组 | 只保留必要历史信息，接近流式计算 |
| 完全背包问题 | 前缀和式优化 | 对一批相似转移做累积合并 |
部分 1D/1D 问题 | 斜率优化 | 在二维凸包上求线性函数极值 |
| 线性递推类问题 | 矩阵加速 | 快速幂 |
| 状态压缩类 DP | 状态设计 | 编码、解码、搜索 |
| 决策单调性 DP | 分治/整体二分等离线技巧 | 利用最优决策位置的单调性 |
因此，学习 DP 优化时不要只记“某某优化模板”。更重要的是问：
这个转移式中的瓶颈，能不能转化成一个我已经熟悉的数据结构或算法问题？
例如：
max/min一堆线性函数，可能联想到凸包；- 多次区间求和，可能联想到前缀和；
- 只依赖上一层状态，可能联想到滚动数组；
- 线性递推求很大项，可能联想到矩阵快速幂。
18. 总结：从题型走向模型
这份 slide 最重要的价值，不是列出了多少 DP 题型，而是提供了一种看待动态规划的分类方式。
可以把三类模型总结成下面这张表：
| 模型 | 核心问题 | 典型状态 | 典型例子 |
|---|---|---|---|
| 固定多阶段决策类 DP | 每个阶段做什么决策 | F[i][state] | 组合数、0/1 背包、数位 DP |
| 路径规划类 DP | 当前走到哪里，路径如何延伸 | dist[v]、F[i][v] | Bellman-Ford、Floyd-Warshall、DAG 最短路 |
| 扩展边界类 DP | 已处理部分和未处理部分的边界状态是什么 | 区间、子树、割集状态 | 区间 DP、树形 DP、插头 DP |
当你遇到一个新的 DP 问题时，可以按下面的顺序思考：
- 能否按固定顺序处理对象？ 例如物品、字符、数位、时间。能的话，先考虑固定多阶段决策类 DP。
- 能否把状态和转移看成图上的点和边？ 能的话，考虑路径规划类 DP。
- 问题是否有图状结构，且存在小边界？ 能的话，考虑扩展边界类 DP。
- 状态里到底要保留什么？ 只保留会影响后续决策的信息。
- 转移瓶颈能否转化成其他算法问题？ 例如前缀和、凸包、矩阵快速幂、分治等。
一句话概括：
动态规划的难点不在于写出
for循环，而在于找到可以合并历史影响的状态。
只要这个状态找对了，转移方程通常就会自然出现；如果状态找错了，再熟悉模板也很难救回来。