动态规划入门

在正式讲一系列概念之前，我们需要先知道：什么是“动态规划”。

动态规划可以理解成：沿着“某个方向”进行递推。至于这个“方向”具体是什么，后文会继续解释。

既然是递推，那么就需要有一个“数组”来存储我们递推过程中得到的信息。这个数组，就是动态规划中最关键的 DP 数组。

递推的本质，是通过一系列“小问题”推出“大问题”。动态规划也是一样：我们先解决一些规模较小、情况较简单的问题，再利用这些结果，推出更大的问题。

---

一、状态

接下来引入第一个概念：状态。

对于简单的动态规划题目来说，状态通常可以设计成：

在“某种情况”下的最优答案。

例如，有 $n$ 个数字需要依次做决策，那么我们可以把状态设计成：

前 $x$ 个数字已经做完决策时，能够得到的最优解。

对于一些更复杂的动态规划题目，状态不一定直接表示答案，也可以表示：

在“某种情况”下，我们需要保存的某些信息。

之后再通过这些信息，进一步求出最终答案。本文暂时不展开复杂情况。

为了方便理解，我们可以把每个“状态”看成图中的一个点。这个点里面存储的值，就是当前状态对应的答案或信息。

也就是说：

状态是点，DP 数组存的就是这个点上的值。

例如，$dp[i]$ 就可以看成编号为 $i$ 的点上存储的值。

---

二、操作

接下来是第二个概念：操作。

这里的“操作”，不是指一整套复杂的过程，而是指最小的操作单元。我通常会把它称为“走一步”（上过课的应该有印象）。

那么，什么叫“最小”呢？

可以这样理解：

在状态图中，一个点通过一步操作，到达另一个点。

也就是说，一个状态可以通过一次操作变成另一个状态。在图中，这一步操作就可以看成一条 有向边。

例如：

$$状态 A \rightarrow 状态 B$$

表示：

从状态 $A$ 可以通过一步操作走到状态 $B$。

因此，动态规划其实可以理解成：

在状态图上，通过操作来建边，然后按照一定顺序计算每个状态的值。

从这个角度看，很多动态规划问题都很像在状态图上做某种“最短路”“最长路”或“路径计数”。

---

三、转移

有了“状态”和“操作”之后，第三个概念：转移，就很好理解了。

所谓转移，就是：

从一个状态出发，通过某个操作，到达另一个状态，并且更新另一个状态中的值。

也可以理解成：

从一个点，沿着一条有向边，走到另一个点，并改变那个点存储的答案。

这就是动态规划中的“状态转移”。

例如：

$$dp[v] = \max(dp[v], dp[u] + w)$$

可以理解成：

从点 $u$ 走到点 $v$，这条边的边权是 $w$，于是尝试用 $dp[u] + w$ 更新 $dp[v]$。

所以动态规划里的“转移方程”，本质上就是在描述：

图中哪些点之间有边，以及沿着这些边走时，点上的值如何变化。

---

四、动态规划的本质

到这里，我们可以把动态规划理解成：

在“操作方向”上的递推。

状态表示当前走到了哪里，操作表示下一步可以怎么走，转移表示走过去之后如何更新答案。

所以，动态规划并不是一个特别神秘的东西。它本质上就是：

把问题拆成很多状态，然后按照某个方向，把这些状态一个一个推出来。

如果从图的角度理解，就是：

把每个状态看成一个点，把每个操作看成一条边，然后在这个状态图上求答案。

有些题目是在状态图上求最大路径权值。

有些题目是在状态图上求最小路径权值。

有些题目是在状态图上求路径数量。

因此，动态规划可以看成：

在一个特殊的状态图上做递推。

这里说它“特殊”，是因为动态规划中的状态图通常是有方向、有顺序的。我们会按照某种顺序，把前面的状态先算出来，再用它们去更新后面的状态。

---

五、几个抽象概念的直观解释

有了“状态图”的理解之后，我们就可以更直观地解释动态规划中的几个抽象概念。

---

1. 重叠子问题

什么是“子问题”？

在状态图中，每一个状态都可以看成一个子问题。

什么是“重叠”？

就是有很多种情况都会到达同一个状态。

换句话说，在状态图中，这个点的入度比较多。

例如，状态 $dp[i]$ 可能既可以由 $dp[i-1]$ 转移过来，也可以由 $dp[i-2]$ 转移过来：

$$i-1 \rightarrow i$$

$$i-2 \rightarrow i$$

多个小问题都会用到同一个状态，这就是重叠子问题。

动态规划之所以要用数组存储答案，就是为了避免重复计算这些状态。

从图上看，就是：

一个点可能会被很多条边指向，所以我们把这个点的答案存下来，后面再用的时候就不用重新算了。

---

2. 无后效性

无后效性指的是：

一个状态一旦确定，它接下来能产生什么影响，只和这个状态本身有关，和它是怎么来的无关。

也就是说，不管当前状态是从哪个状态转移过来的，只要当前状态相同，那么它之后能够转移到哪些状态、产生什么贡献，都是一样的。

从图上看，就是：

只要到达了同一个点，那么从这个点出发的边就是固定的。

它不会因为你是从哪条边走过来的，就突然多出一些边，或者少掉一些边。

举个例子：

假设当前状态是“我饱了”，接下来要进行“消化”操作。

如果“吃饭吃饱”和“吃面吃饱”之后，消化时间完全一样，那么我们只需要记录“饱了”这个状态即可。

但如果吃饭和吃面的消化时间不一样，那么虽然当前都叫“饱了”，但它们之后的发展并不相同。

此时只记录“饱了”就不够了，因为状态还受到之前选择的影响，这就存在后效性。

所以，动态规划的状态设计必须保证：

当前状态包含了影响未来决策所需要的全部信息。

如果从图上理解，就是：

一个点能走向哪里，必须只由这个点本身决定，而不能依赖它是怎么走到这个点的。

---

3. 最优子结构

最优子结构指的是：

大问题的最优解，可以由小问题的最优解推出来。

放到状态图里理解，就是：

当一个点的所有前置状态都计算完成后，我们就可以利用这些前置状态，推出当前点的最优值。

例如，如果有三条边指向点 $v$：

$$u_1 \rightarrow v$$

$$u_2 \rightarrow v$$

$$u_3 \rightarrow v$$

那么我们只需要知道 $u_1,u_2,u_3$ 这些点的最优值，就可以计算出 $v$ 的最优值。

如果整个状态图是一个 DAG，也就是有向无环图，那么我们就可以按照某种顺序，从前往后把所有状态依次算出来。

这也是为什么动态规划通常需要确定一个“递推顺序”。

因为只有当前面的小问题都算完了，我们才能放心地去计算后面的大问题。

从图上理解就是：

一个点要等它前面的点都算完，才能开始计算自己。

---

六、动态规划的步骤

有了前面的概念之后，我们再来看做动态规划题目的一般步骤。

---

1. 识别问题类型

首先要判断这道题是否适合用动态规划。

动态规划常见于两类问题：

最优化问题和计数问题。

所谓最优化问题，就是要求最大值、最小值、最少次数、最多方案、最小代价等。

例如：

• 最多能得到多少分；
• 最少需要多少步；
• 最小花费是多少；
• 最大收益是多少。

所谓计数问题，就是要求方案数。

例如：

• 有多少种走法；
• 有多少种选择方式；
• 有多少种合法方案。

当然，不是所有最优化问题和计数问题都一定是动态规划，但如果题目中出现了“前面怎么选会影响后面”“可以由小规模推出大规模”这类感觉，就可以优先往动态规划方向考虑。

从图上看，动态规划常见的目标就是：

• 求到达某个点的最大路径权值；
• 求到达某个点的最小路径权值；
• 求到达某个点的路径数量。

---

2. 设计状态

接下来要设计状态，也就是确定 DP 数组的含义。

从图的角度看，这一步就是：

确定图中的点是什么。

对于简单动态规划来说，可以先用一个比较直接的方法：

答案问什么，状态就尽量往什么方向设计。

例如，题目问“前 $n$ 个数能得到的最大值”，我们就可以先尝试设计：

$$dp[i]$$

表示：

前 $i$ 个数已经处理完时，能够得到的最优答案。

如果题目问“走到第 $n$ 级台阶有多少种方法”，我们就可以设计：

$$dp[i]$$

表示：

走到第 $i$ 级台阶的方案数。

也就是说，状态设计的第一步，不需要一开始就非常复杂，可以先从题目最终要求的答案出发。

---

3. 识别操作

状态设计出来之后，下一步是识别“操作”。

从图的角度看，这一步就是：

确定点和点之间有哪些边。

也就是思考：

当前状态可以通过哪些“一步操作”转移到其他状态？

或者反过来思考：

当前状态可以由哪些前面的状态转移过来？

例如，走楼梯问题中，如果每次可以走 $1$ 级或 $2$ 级，那么：

• 从第 $i-1$ 级可以走一步到第 $i$ 级；
• 从第 $i-2$ 级可以走一步到第 $i$ 级。

所以图中就有两类边：

$$i-1 \rightarrow i$$

$$i-2 \rightarrow i$$

状态是点，操作是边。

---

4. 确定转移方式

找到前驱状态之后，还要确定这些前驱状态如何合并成当前状态。

从图的角度看，这一步就是：

多条边指向同一个点时，这个点的值应该怎么更新。

有些题目是求方案数，那么通常是把所有可能来源加起来：

$$dp[i] = dp[i-1] + dp[i-2]$$

这相当于：

到达点 $i$ 的路径数量，等于所有能走到点 $i$ 的前驱点的路径数量之和。

有些题目是求最大值，那么通常是在所有来源中取最大：

$$dp[v] = \max(dp[v], dp[u] + w)$$

这相当于：

从所有能走到点 $v$ 的边中，选出一条收益最大的路径。

有些题目是求最小值，那么通常是在所有来源中取最小：

$$dp[v] = \min(dp[v], dp[u] + w)$$

这相当于：

从所有能走到点 $v$ 的边中，选出一条代价最小的路径。

因此，确定转移方式时，要看题目最终问的是什么：

• 问方案数，通常是加法；
• 问最大值，通常是取 $\max$；
• 问最小值，通常是取 $\min$。

当然，真实题目里不一定这么简单，但这个方向是最常见的。

---

5. 检查状态是否足够

在写转移时，经常会遇到一种情况：

明明状态设计出来了，但是发现转移写不出来。

这通常说明一个问题：

当前状态记录的信息不够。

也就是说，只用现在这个 DP 数组，无法判断下一步应该怎么走，或者无法确定当前状态的答案。

从图上看，就是：

你现在设计出来的点不够细，导致从这个点出发时，不知道有哪些边是合法的，或者边权不唯一（也就是存在后效性）。

这时，最简单，最直接，最不绕弯子，最暴力的就是把状态设计得更细致一些。

例如，原本只设计：

$$dp[i]$$

表示前 $i$ 个位置的最优答案。

但是后来发现，第 $i$ 个位置选没选，会影响后面的选择。

那么就可以多加一个维度：

$$dp[i][0], dp[i][1]$$

其中：

• $dp[i][0]$ 表示前 $i$ 个位置处理完，并且第 $i$ 个位置不选时的最优答案；
• $dp[i][1]$ 表示前 $i$ 个位置处理完，并且第 $i$ 个位置选择时的最优答案。

这样一来，状态点就从一类变成了两类：

$$(i, 0), (i, 1)$$

点变细之后，边也就更清楚了。

所以，动态规划的状态并不一定是一开始就能完美设计出来的。很多时候，我们是在尝试写转移的过程中，发现信息不够，然后再反过来修改状态。

可以总结成一句话（这句对于很多动态规划有着醍醐灌顶的作用，用过都说好）：

转移缺什么，状态就补什么。

---

6. 按顺序求解

最后一步，就是按照正确的顺序计算所有状态。

因为动态规划是用小问题推出大问题，所以我们必须保证：

计算当前状态之前，它依赖的状态已经算完了。

例如，$dp[i]$ 依赖 $dp[i-1]$ 和 $dp[i-2]$，那么我们就应该从小到大枚举 $i$。

从状态图的角度看，这其实就是在按照图上的依赖关系求解。

如果把每个状态看成一个点，把转移看成一条有向边，那么我们要做的就是：

按照有向边的方向，把所有状态依次算出来。

这个顺序本质上就是一种拓扑顺序。

对于初学阶段，可以先简单理解成：

前面的状态先算，后面的状态再用前面的结果。

---

七、例题

下面通过几个经典例题，来对应前面讲过的几个概念。

---

第一题：走楼梯

假设一共有 $n$ 级台阶，每次可以走 $1$ 级或 $2$ 级，问走到第 $n$ 级台阶有多少种方法。

这是一道非常典型的计数型动态规划。

---

1. 状态是点

我们可以设计状态：

$$dp[i]$$

表示：

走到第 $i$ 级台阶的方案数。

从图的角度看，每一级台阶都是一个点。

点 $i$ 表示：

当前已经走到了第 $i$ 级台阶。

---

2. 操作是边

每次可以走 $1$ 级或 $2$ 级，这也是我们能做的最小操作。

所以：

• 从第 $i-1$ 级可以走 $1$ 级到第 $i$ 级；
• 从第 $i-2$ 级可以走 $2$ 级到第 $i$ 级。

也就是图中有两条边：

$$i-1 \rightarrow i$$

$$i-2 \rightarrow i$$

这些边表示“走一步”的操作。

---

3. 转移是统计路径数量

因为题目问的是方案数，所以我们要求的是：

从起点走到点 $i$ 的路径数量。

所有能走到点 $i$ 的路径，都一定来自：

• 点 $i-1$；
• 点 $i-2$。

所以：

$$dp[i] = dp[i-1] + dp[i-2]$$

这里的加法表示：

到达点 $i$ 的路径数量，等于所有前驱点的路径数量之和。

---

4. 小结

走楼梯从状态图角度理解就是：

• 点：第 $i$ 级台阶；
• 边：走 $1$ 级或走 $2$ 级；
• $dp[i]$：到达点 $i$ 的路径数量；
• 目标：求到达点 $n$ 的路径数量。

---

第二题：打家劫舍

假设有一排房子，每个房子里有一些钱。小偷不能偷相邻的两个房子，问最多能偷多少钱。

这是一道典型的最优化动态规划。

这道题的关键限制是：

不能偷相邻的两个房子。

也就是说，当我们走到第 $i$ 个房子时，能不能偷它，取决于前一个房子有没有被偷。

所以我们不能只把状态设计成“处理到第 $i$ 个房子”，还需要记录当前这个房子是否被偷。

---

1. 状态是点

从图的角度来看，我们可以把每个状态看成一个点：

$$(i, 0), (i, 1)$$

其中：

• $(i, 0)$ 表示：处理完前 $i$ 个房子，并且第 $i$ 个房子不偷；
• $(i, 1)$ 表示：处理完前 $i$ 个房子，并且第 $i$ 个房子偷。

对应到 DP 数组中就是：

$$dp[i][0], dp[i][1]$$

其中：

• $dp[i][0]$ 表示到达状态 $(i, 0)$ 时，能够得到的最大金额；
• $dp[i][1]$ 表示到达状态 $(i, 1)$ 时，能够得到的最大金额。

这里之所以要拆成两个点，是因为：

第 $i$ 个房子偷没偷，会影响后面的边怎么连。

如果只用一个点表示“处理到第 $i$ 个房子”，我们就不知道第 $i+1$ 个房子还能不能偷。

---

2. 操作是边

接下来考虑状态之间的边，也就是一步操作。

---

如果第 $i$ 个房子不偷，那么第 $i-1$ 个房子偷不偷都可以。

所以图中有两条边：

$$(i-1, 0) \rightarrow (i, 0)$$

$$(i-1, 1) \rightarrow (i, 0)$$

这两条边表示：

不管前一个房子偷没偷，我现在这个房子都可以选择不偷。

因为第 $i$ 个房子不偷，所以金额不会增加。

---

如果第 $i$ 个房子偷，那么第 $i-1$ 个房子一定不能偷。

所以图中只有一条边：

$$(i-1, 0) \rightarrow (i, 1)$$

这条边表示：

只有当前一个房子不偷时，我现在这个房子才能偷。

因为偷了第 $i$ 个房子，所以金额会增加 $a[i]$。

---

3. 转移是求最大路径权值

现在我们把每条边看成一次选择。

• 选择“不偷第 $i$ 个房子”，边权是 $0$；
• 选择“偷第 $i$ 个房子”，边权是 $a[i]$。

那么这道题就变成了：

在状态图中，从左往右走，求能获得的最大路径权值。

如果走到 $(i,0)$，说明第 $i$ 个房子不偷。

它可以从两个状态转移过来：

$$(i-1,0) \rightarrow (i,0)$$

$$(i-1,1) \rightarrow (i,0)$$

所以：

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1])$$

如果走到 $(i,1)$，说明第 $i$ 个房子偷。

它只能从 $(i-1,0)$ 转移过来：

$$(i-1,0) \rightarrow (i,1)$$

所以：

$$dp[i][1] = dp[i-1][0] + a[i]$$

---

4. 最终答案

处理完所有房子后，最后一个房子可以偷，也可以不偷。

所以答案是两个终点状态中的最大值：

$$\max(dp[n][0], dp[n][1])$$

---

5. 小结

打家劫舍从状态图角度理解就是：

• 点：$(i,0)$ 和 $(i,1)$；
• 边：表示第 $i$ 个房子偷或不偷；
• 边权：偷则增加 $a[i]$，不偷则增加 $0$；
• $dp[i][0]$：到达点 $(i,0)$ 的最大收益；
• $dp[i][1]$：到达点 $(i,1)$ 的最大收益；
• 目标：求所有终点状态中的最大路径权值。

这就是“状态细化”的思想：

当一个状态无法确定后续能走哪些边时，就要把状态拆得更细。

在本题中，转移时缺少的信息是“当前房子有没有被偷”，所以我们增加了一维状态来记录这个信息。

---

第三题：找零问题

假设有若干种硬币面值，每种硬币可以使用无限次。现在要凑出金额 $n$，问最少需要多少枚硬币。

这是一道最小值动态规划。

---

1. 状态是点

我们可以设计状态：

$$dp[i]$$

表示：

凑出金额 $i$ 最少需要多少枚硬币。

从图的角度看，每一个金额都是一个点。

点 $i$ 表示：

当前已经凑出了金额 $i$。

---

2. 操作是边

每次我们可以选择一枚硬币。

假设这枚硬币的面值是 $v$。

如果当前已经凑出了金额 $i-v$，再加入一枚面值为 $v$ 的硬币，就可以凑出金额 $i$。

所以图中有一条边：

$$i-v \rightarrow i$$

这条边表示：

选择一枚面值为 $v$ 的硬币。

因为使用了一枚硬币，所以这条边的边权是 $1$。

---

3. 转移是求最短路径

由于题目问的是最少需要多少枚硬币，所以我们要求的是：

从金额 $0$ 走到金额 $n$ 的最短路径长度。

如果最后一枚硬币的面值是 $v$，那么它一定是从金额 $i-v$ 转移到金额 $i$。

因此：

$$dp[i] = \min(dp[i], dp[i-v] + 1)$$

这里的 $+1$ 表示：

又使用了一枚硬币。

这里的 $\min$ 表示：

在所有能够到达金额 $i$ 的方式中，选择硬币数量最少的一种。

---

4. 小结

找零问题从状态图角度理解就是：

• 点：金额 $i$；
• 边：选择一枚硬币；
• 边权：每选一枚硬币，代价为 $1$；
• $dp[i]$：从金额 $0$ 到金额 $i$ 的最短路径长度；
• 目标：求从 $0$ 到 $n$ 的最短路径长度。

所以找零问题本质上就是：

在金额构成的状态图上，求到达目标金额的最小代价。

最后，感谢 $\text{codex}$ 先生的润色。