动态规划入门

pangz

2026-07-02 11:01:17

发布于：浙江

22阅读

0回复

0点赞

动态规划入门

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

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

既然是递推，那么就需要有一个“数组”来存储我们递推过程中得到的信息。这个数组，就是动态规划中最关键的 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}$ 先生的润色。

有帮助，赞一个

去预览

0/2000

全部评论 1

Eucatastrophe‌
在最不会动态规划的年纪看见入门贴

2026-07-02 来自浙江
0

动态规划入门

一、状态

二、操作

三、转移

四、动态规划的本质

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

1. 重叠子问题

2. 无后效性

3. 最优子结构

六、动态规划的步骤

1. 识别问题类型

2. 设计状态

3. 识别操作

4. 确定转移方式

5. 检查状态是否足够

6. 按顺序求解

七、例题

第一题：走楼梯

1. 状态是点

2. 操作是边

3. 转移是统计路径数量

4. 小结

第二题：打家劫舍

1. 状态是点

2. 操作是边

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

4. 最终答案

5. 小结

第三题：找零问题

1. 状态是点

2. 操作是边

3. 转移是求最短路径

4. 小结

全部评论 1

热门讨论