动态规划经典模型：从状态、决策到三类 DP 模型

学习动态规划时，我们经常会一次接触到很多题型，比如背包、区间 DP、树形 DP、数位 DP、插头 DP、最短路和状态压缩等，可只记住题型名称并不太够，换一道没见过的题，还是可能判断不出它属于哪种模型，也说不清状态为什么要那样设计。

我觉得更顺手的理解方式是，动态规划并不是上来就背转移方程，而是把原问题拆成一批具有相同后效性的子问题；大量具体的决策前缀只要能被合并成有限个“状态”，并且归到同一状态的前缀对后续决策有相同影响，就能把原本庞大的枚举量压下来。

按照这份 slide 的思路，动态规划可以整理为三个经典模型：

  1. 固定多阶段决策类动态规划
  2. 路径规划类动态规划
  3. 扩展边界类动态规划

这三个名称不是互相排斥的“标签”，一道题完全可能同时从不同角度理解，它们更像三种观察 DP 的方式，分别关心 阶段怎样推进、路径如何延伸、边界如何扩张。

1. 动态规划到底在做什么

动态规划经常被用于组合优化与计数问题，其基本想法可以写成：

将原问题拆成若干子问题，并且每个子问题都能用几个更简单子问题的解快速得到。

这句话听上去和分治、递推、递归都有些相似，不过动态规划不只负责把问题“拆开”，还要把其中 重复出现的子问题合并起来。

暴力搜索往往要保留并枚举完整的决策过程，其中可能包括：

  • 前面几步分别选了什么
  • 当前已经形成了怎样的局面
  • 从这个局面出发，后面还可以怎样继续

动态规划会把对后续影响完全相同的若干决策前缀归并到同一个状态，合并以后，不再追究每个前缀具体是怎样走来的，只保留这个状态对应的最优值、方案数或可行性。

从这个角度看，DP 主要处理四件事：

  1. 定义阶段：问题目前推进到了哪里
  2. 定义状态：为了决定后面的动作，当前必须留下哪些信息
  3. 设计决策：从现有状态出发可以作出哪些选择
  4. 合并影响：把后效性相同的决策前缀收进同一状态

2. 固定多阶段决策类动态规划

比较直观的一类动态规划是 固定多阶段决策类 DP。

这类问题通常能划出明确的阶段，每个阶段都要完成一次或若干次决策，当前状态再加上本轮决策，共同决定下一阶段会进入哪个状态。

可以抽象成下面这个过程：

阶段 i 的状态
    + 当前阶段的决策
        -> 阶段 i + 1 的状态

这个模型能成立，依赖下面几件事：

  • 前 i 个阶段产生的每一种有效决策前缀，都能落到阶段 i 的某个状态中
  • 落在同一状态的决策前缀，会对后续选择产生相同影响
  • 原本“枚举每一种决策前缀”的做法，因而可以改成“枚举状态以及下一步决策”

组合数计算、0/1 背包与数位 DP，都可以从这个模型切入。

3. 例一：组合数计算

先看一个简单问题，有 n 个彼此可区分的球，需要从中拿出 m 个，求一共有多少种不同拿法。

可以把所有球排成一列，再从左到右逐个处理，每碰到一个球都要作出一次选择：

  • 拿这个球
  • 不拿这个球

于是，“已经处理到第几个球”构成阶段，“目前一共拿了几个球”则是需要保留的状态。

设：

F[i][j] F[i][j]

它表示只看前 i 个球时，恰好取出 j 个球共有多少种方案。

按照后向性思考，当前若已经处理完前 i 个球，并且从中取了 j 个，接下来面对第 i + 1 个球时就有两种选择：

  1. 拿第 i + 1 个球，进入状态 (i + 1, j + 1)
  2. 不拿第 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 个

因此有：

F[i][j]=F[i−1][j−1]+F[i−1][j] F[i][j] = F[i - 1][j - 1] + F[i - 1][j]

这就是组合数递推式，真正起作用的是公式背后的状态压缩，我们把“具体拿了哪些球”丢掉，只留下“处理到第几个球”和“已经拿了几个球”，而这些信息已经足够完成后面的决策。

4. 后向性思考与前向性思考

设计动态规划转移时，常用的思考方向有两种。

一方面，可以采用 后向性思考：

从一个已知状态出发，枚举所有可能的下一步决策，然后把影响传递给后继状态。

这种写法像是“从当前状态向外扩展”，在组合数例子中，就是由 F[i][j] 走到 F[i + 1][j] 与 F[i + 1][j + 1]。

另一方面，也可以使用 前向性思考：

目标是求解某个状态，考虑它可能由哪些上一个状态和上一个决策转移而来。

此时更像“计算当前状态时向前追溯”，组合数中的写法就是：

F[i][j]=F[i−1][j−1]+F[i−1][j] F[i][j] = F[i - 1][j - 1] + F[i - 1][j]

多数情况下，两种思路面对的难点并没有差多少，真正需要想明白的是：

  • 状态中到底要保存哪些信息
  • 哪些历史信息已经可以合并
  • 哪些历史仍会影响后面的决策，暂时还不能丢

5. 例二：0/1 背包问题

0/1 背包是固定多阶段决策类 DP 中很典型的模型。

问题给出 n 个物品，第 i 个物品重 w_i、价值为 v_i，背包容量是 W，每件物品最多只能取一次，需要求出总重量不超过 W 时能够获得的最大总价值。

仍然把物品排成一列并从左到右处理，每轮只需要决定：

  • 拿当前物品
  • 不拿当前物品

“处理到第几个物品”是阶段，“当前总重量是多少”则构成状态。

设：

F[i][j] F[i][j]

它表示从前 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]
)

时间复杂度是：

O(nW) O(nW)

常见的背包讲解会直接把状态定义为“前 i 个物品中，总重量不超过 j 的最大价值”，随后马上压成一维滚动数组并采用倒序更新；代码确实很简洁，可状态定义、阶段压缩和实现技巧被放到了一起，刚接触时容易只记住模板，却没有看清决策是怎样发生的。

刚开始学习时，可以先从二维状态把三件事分开：

阶段：处理到第几个物品
状态：当前总重量是多少
决策：拿或不拿

等这个模型真正清楚了，再看滚动数组与倒序更新，就能知道每一步优化删掉了什么，而不是只会照着模板敲。

6. 固定多阶段决策类 DP 的常见题型

这一类 DP 有一个很明显的特征：阶段按固定顺序推进，而且每个阶段都有决策要做。

常见题型有：

  • 背包问题：按照顺序决定每种物品选不选、选多少
  • 数位 DP：模拟加法电路，依次处理每一位数字上的决策
  • 其他带有明确时间、位置、物品序列或字符序列的 DP

判断时可以先问自己：

我能不能把问题拆成“处理第 1 个对象、处理第 2 个对象、……、处理第 n 个对象”？

如果确实能这样拆开，而且前面步骤留下的影响可以由有限状态表示，这道题大概率就能用固定多阶段决策类 DP 来理解。

7. 路径规划类动态规划

另一个常见视角是 路径规划类动态规划。

这类模型经常出现在图论路径问题中，典型算法有：

  • Bellman-Ford
  • Floyd-Warshall
  • Dijkstra
  • DAG 最短路

与固定多阶段决策类相比，路径规划类问题的阶段通常没有那么直观，路径长度可能并不固定，位置变化也未必按线性顺序推进。

不过它们往往有一个共同点：

对后续影响最关键的信息，通常是当前所在的位置。

许多时候，我们不需要保留“具体沿哪条路线走到了这里”，真正会影响后续转移的是当前落在哪个点，以及到达这个点时已经得到的最优代价。

8. 例一：Bellman-Ford 算法

给定一张有向带权图，边权允许为负，但图中保证没有负环，现在要求源点 s 到所有可达点的最短路径长度。

因为不存在负环，最短路径可以按简单路径处理，于是“已经使用的边数”就能被拿来离散化阶段。

设：

F[i][v] F[i][v]

它表示从源点 s 走到点 v，并且使用边数不超过 i 时的最短路径长度；若这样的路径不存在，就记成 +∞。

要计算使用边数不超过 i + 1 时到达 v 的最短路，可以枚举抵达 v 前经过的边 (u, v)，从而得到：

F[i+1][v]=min⁡(F[i][v], F[i][u]+wu,v),(u,v)∈E F[i + 1][v] = \min\left(F[i][v],\ F[i][u] + w_{u,v}\right),\quad (u, v) \in E

这个转移包含两种可能：

  • 不加入新边，直接沿用已有的 F[i][v]
  • 先用不超过 i 条边到达某个 u，再沿一条新边走到 v

把阶段维度用滚动数组压缩以后，就得到了常见的 Bellman-Ford 算法形式。

9. 例二：Floyd-Warshall 算法

Floyd-Warshall 可以求出任意点对之间的最短路径。

它并不按照路径长度划分阶段，而是把“允许经过哪些中间点”作为阶段，这种离散方式与前面的例子不太一样。

设：

F[k][i][j] F[k][i][j]

它表示从 i 走到 j，且途中所有中间点都只能取自集合 {1, 2, ..., k} 时的最短路径长度。

把第 k + 1 个点加入可选中转点后，最短路会落在两种情况中：

  1. 最短路没有经过 k + 1，答案仍是 F[k][i][j]
  2. 最短路经过了 k + 1，路径可以拆为 i -> k + 1 与 k + 1 -> j 两段

因此：

F[k+1][i][j]=min⁡(F[k][i][j], F[k][i][k+1]+F[k][k+1][j]) F[k + 1][i][j] = \min\left(F[k][i][j],\ F[k][i][k + 1] + F[k][k + 1][j]\right)

再用滚动方式去掉第一维，就能得到常见的 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 的最小总代价。

设：

F[j] F[j]

它记录从 1 一路跳到 j 所需的最小代价。

计算时只要枚举上一步所在的位置 i：

F[j]=min⁡i<j(F[i]+w(i,j)) F[j] = \min_{i < j}\left(F[i] + w(i, j)\right)

把每个位置当成点，再把允许从 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 是否被选，子树内部具体怎样组合可以不再保留。

取任意点为根，设：

F[u][0] F[u][0]

它表示在以 u 为根的子树中，不选择 u 时能得到的最大权独立集权值；

F[u][1] F[u][1]

它表示同一棵子树中，选择 u 时能得到的最大权独立集权值。

当 u 不被选择时，每个子节点 v 都可以从选与不选两种结果里取较大值：

F[u][0]=∑v 是 u 的子节点max⁡(F[v][0],F[v][1]) F[u][0] = \sum_{v \text{ 是 } u \text{ 的子节点}} \max(F[v][0], F[v][1])

当 u 被选中后，所有子节点 v 都只能使用不选自身的状态：

F[u][1]=weight[u]+∑v 是 u 的子节点F[v][0] F[u][1] = weight[u] + \sum_{v \text{ 是 } u \text{ 的子节点}} F[v][0]

树形 DP 并不只是“在树上写递归”，更重要的是各个子问题天然会被边界节点隔开，只要把边界节点的状态记下来，就能安全地合并不同子树的答案。

14. 例二：合并石子问题

现在有 n 堆石子，第 i 堆包含 a_i 个，每次只能选择相邻的两堆进行合并，操作代价等于两堆石子的总数，需要求出把所有石子合成一堆的最小总代价。

无论合并到了哪一步，当前任意一堆石子都必然对应原序列中的某个连续区间，例如其中一堆可能由最初第 i 堆到第 j 堆逐步合并而来。

利用这个性质，可以定义区间状态：

F[i][j] F[i][j]

它记录把第 i 堆到第 j 堆全部合并为一堆所需的最小代价。

若收尾步骤完成了整个区间 [i, j] 的合并，那么操作发生前，它一定由两个相邻区间组成：

  • [i, k]
  • [k + 1, j]

于是有：

F[i][j]=min⁡i≤k<j(F[i][k]+F[k+1][j]+∑l=ijal) F[i][j] = \min_{i \le k < j}\left(F[i][k] + F[k + 1][j] + \sum_{l=i}^{j} a_l\right)

式子里的三部分分别表示：

  • 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 场景常见优化背后对应的问题
一般动态规划问题滚动数组只保留必要历史信息，接近流式计算
完全背包问题前缀和式优化对一批相似转移做累积合并
部分 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 问题，可以从这几个方面逐步检查：

  1. 能否按固定顺序处理对象？ 对象可能是物品、字符、数位或时间，若能依次处理，可以考虑固定多阶段决策类 DP
  2. 状态与转移能否看成图上的点和边？ 如果能，路径规划类 DP 往往更容易解释这个过程
  3. 问题是否具有图状结构，并且存在小边界？ 满足时可以尝试扩展边界类 DP
  4. 状态究竟需要保留什么？ 只留下仍会影响后续决策的信息，已经没有影响的历史要及时合并
  5. 转移瓶颈能否换成其他算法问题？ 可以从前缀和、凸包、矩阵快速幂、分治等方向寻找优化办法

整篇内容可以收在一句话里：

动态规划的难点不在于写出 for 循环，而在于找到可以合并历史影响的状态。

状态找得合适，转移方程往往会顺着决策关系自然出现；状态定义若从一开始就丢了必要信息，后面即使再熟悉模板，也很难把问题补回来。