动态规划入门
2026-07-02 11:01:17
发布于：浙江
动态规划入门
在正式讲一系列概念之前，我们需要先知道：什么是“动态规划”。
动态规划可以理解成：沿着“某个方向”进行递推。至于这个“方向”具体是什么，后文会继续解释。
既然是递推，那么就需要有一个“数组”来存储我们递推过程中得到的信息。这个数组，就是动态规划中最关键的 DP 数组。
递推的本质，是通过一系列“小问题”推出“大问题”。动态规划也是一样：我们先解决一些规模较小、情况较简单的问题，再利用这些结果，推出更大的问题。
一、状态
接下来引入第一个概念：状态。
对于简单的动态规划题目来说，状态通常可以设计成：
在“某种情况”下的最优答案。
例如，有 个数字需要依次做决策，那么我们可以把状态设计成：
前 个数字已经做完决策时，能够得到的最优解。
对于一些更复杂的动态规划题目，状态不一定直接表示答案，也可以表示：
在“某种情况”下，我们需要保存的某些信息。
之后再通过这些信息，进一步求出最终答案。本文暂时不展开复杂情况。
为了方便理解，我们可以把每个“状态”看成图中的一个点。这个点里面存储的值，就是当前状态对应的答案或信息。
也就是说：
状态是点，DP 数组存的就是这个点上的值。
例如， 就可以看成编号为 的点上存储的值。
二、操作
接下来是第二个概念：操作。
这里的“操作”，不是指一整套复杂的过程，而是指最小的操作单元。我通常会把它称为“走一步”（上过课的应该有印象）。
那么，什么叫“最小”呢？
可以这样理解：
在状态图中，一个点通过一步操作，到达另一个点。
也就是说，一个状态可以通过一次操作变成另一个状态。在图中，这一步操作就可以看成一条 有向边。
例如：
表示：
从状态 可以通过一步操作走到状态 。
因此，动态规划其实可以理解成：
在状态图上，通过操作来建边，然后按照一定顺序计算每个状态的值。
从这个角度看，很多动态规划问题都很像在状态图上做某种“最短路”“最长路”或“路径计数”。
三、转移
有了“状态”和“操作”之后，第三个概念：转移，就很好理解了。
所谓转移，就是：
从一个状态出发，通过某个操作，到达另一个状态，并且更新另一个状态中的值。
也可以理解成：
从一个点，沿着一条有向边，走到另一个点，并改变那个点存储的答案。
这就是动态规划中的“状态转移”。
例如：
可以理解成：
从点 走到点 ，这条边的边权是 ，于是尝试用 更新 。
所以动态规划里的“转移方程”，本质上就是在描述：
图中哪些点之间有边，以及沿着这些边走时，点上的值如何变化。
四、动态规划的本质
到这里，我们可以把动态规划理解成：
在“操作方向”上的递推。
状态表示当前走到了哪里，操作表示下一步可以怎么走，转移表示走过去之后如何更新答案。
所以，动态规划并不是一个特别神秘的东西。它本质上就是：
把问题拆成很多状态，然后按照某个方向，把这些状态一个一个推出来。
如果从图的角度理解，就是：
把每个状态看成一个点，把每个操作看成一条边，然后在这个状态图上求答案。
有些题目是在状态图上求最大路径权值。
有些题目是在状态图上求最小路径权值。
有些题目是在状态图上求路径数量。
因此，动态规划可以看成：
在一个特殊的状态图上做递推。
这里说它“特殊”，是因为动态规划中的状态图通常是有方向、有顺序的。我们会按照某种顺序，把前面的状态先算出来，再用它们去更新后面的状态。
五、几个抽象概念的直观解释
有了“状态图”的理解之后，我们就可以更直观地解释动态规划中的几个抽象概念。
1. 重叠子问题
什么是“子问题”？
在状态图中，每一个状态都可以看成一个子问题。
什么是“重叠”？
就是有很多种情况都会到达同一个状态。
换句话说，在状态图中，这个点的入度比较多。
例如，状态 可能既可以由 转移过来，也可以由 转移过来：
多个小问题都会用到同一个状态，这就是重叠子问题。
动态规划之所以要用数组存储答案，就是为了避免重复计算这些状态。
从图上看，就是：
一个点可能会被很多条边指向，所以我们把这个点的答案存下来，后面再用的时候就不用重新算了。
2. 无后效性
无后效性指的是：
一个状态一旦确定，它接下来能产生什么影响，只和这个状态本身有关，和它是怎么来的无关。
也就是说，不管当前状态是从哪个状态转移过来的，只要当前状态相同，那么它之后能够转移到哪些状态、产生什么贡献，都是一样的。
从图上看，就是：
只要到达了同一个点，那么从这个点出发的边就是固定的。
它不会因为你是从哪条边走过来的，就突然多出一些边，或者少掉一些边。
举个例子：
假设当前状态是“我饱了”，接下来要进行“消化”操作。
如果“吃饭吃饱”和“吃面吃饱”之后，消化时间完全一样，那么我们只需要记录“饱了”这个状态即可。
但如果吃饭和吃面的消化时间不一样，那么虽然当前都叫“饱了”，但它们之后的发展并不相同。
此时只记录“饱了”就不够了，因为状态还受到之前选择的影响，这就存在后效性。
所以，动态规划的状态设计必须保证：
当前状态包含了影响未来决策所需要的全部信息。
如果从图上理解，就是：
一个点能走向哪里，必须只由这个点本身决定，而不能依赖它是怎么走到这个点的。
3. 最优子结构
最优子结构指的是：
大问题的最优解，可以由小问题的最优解推出来。
放到状态图里理解，就是：
当一个点的所有前置状态都计算完成后，我们就可以利用这些前置状态，推出当前点的最优值。
例如，如果有三条边指向点 ：
那么我们只需要知道 这些点的最优值，就可以计算出 的最优值。
如果整个状态图是一个 DAG，也就是有向无环图，那么我们就可以按照某种顺序，从前往后把所有状态依次算出来。
这也是为什么动态规划通常需要确定一个“递推顺序”。
因为只有当前面的小问题都算完了，我们才能放心地去计算后面的大问题。
从图上理解就是：
一个点要等它前面的点都算完，才能开始计算自己。
六、动态规划的步骤
有了前面的概念之后，我们再来看做动态规划题目的一般步骤。
1. 识别问题类型
首先要判断这道题是否适合用动态规划。
动态规划常见于两类问题：
最优化问题和计数问题。
所谓最优化问题，就是要求最大值、最小值、最少次数、最多方案、最小代价等。
例如：
- 最多能得到多少分；
- 最少需要多少步；
- 最小花费是多少；
- 最大收益是多少。
所谓计数问题，就是要求方案数。
例如：
- 有多少种走法；
- 有多少种选择方式；
- 有多少种合法方案。
当然，不是所有最优化问题和计数问题都一定是动态规划，但如果题目中出现了“前面怎么选会影响后面”“可以由小规模推出大规模”这类感觉，就可以优先往动态规划方向考虑。
从图上看，动态规划常见的目标就是：
- 求到达某个点的最大路径权值；
- 求到达某个点的最小路径权值；
- 求到达某个点的路径数量。
2. 设计状态
接下来要设计状态，也就是确定 DP 数组的含义。
从图的角度看，这一步就是：
确定图中的点是什么。
对于简单动态规划来说，可以先用一个比较直接的方法：
答案问什么，状态就尽量往什么方向设计。
例如，题目问“前 个数能得到的最大值”，我们就可以先尝试设计：
表示：
前 个数已经处理完时，能够得到的最优答案。
如果题目问“走到第 级台阶有多少种方法”，我们就可以设计：
表示：
走到第 级台阶的方案数。
也就是说，状态设计的第一步，不需要一开始就非常复杂，可以先从题目最终要求的答案出发。
3. 识别操作
状态设计出来之后，下一步是识别“操作”。
从图的角度看，这一步就是：
确定点和点之间有哪些边。
也就是思考：
当前状态可以通过哪些“一步操作”转移到其他状态？
或者反过来思考：
当前状态可以由哪些前面的状态转移过来？
例如，走楼梯问题中，如果每次可以走 级或 级，那么：
- 从第 级可以走一步到第 级；
- 从第 级可以走一步到第 级。
所以图中就有两类边：
状态是点，操作是边。
4. 确定转移方式
找到前驱状态之后，还要确定这些前驱状态如何合并成当前状态。
从图的角度看，这一步就是：
多条边指向同一个点时，这个点的值应该怎么更新。
有些题目是求方案数，那么通常是把所有可能来源加起来：
这相当于：
到达点 的路径数量，等于所有能走到点 的前驱点的路径数量之和。
有些题目是求最大值，那么通常是在所有来源中取最大：
这相当于：
从所有能走到点 的边中，选出一条收益最大的路径。
有些题目是求最小值，那么通常是在所有来源中取最小：
这相当于：
从所有能走到点 的边中，选出一条代价最小的路径。
因此，确定转移方式时，要看题目最终问的是什么：
- 问方案数，通常是加法；
- 问最大值，通常是取 ；
- 问最小值，通常是取 。
当然，真实题目里不一定这么简单，但这个方向是最常见的。
5. 检查状态是否足够
在写转移时，经常会遇到一种情况：
明明状态设计出来了，但是发现转移写不出来。
这通常说明一个问题：
当前状态记录的信息不够。
也就是说，只用现在这个 DP 数组，无法判断下一步应该怎么走，或者无法确定当前状态的答案。
从图上看，就是：
你现在设计出来的点不够细，导致从这个点出发时，不知道有哪些边是合法的，或者边权不唯一（也就是存在后效性）。
这时，最简单，最直接，最不绕弯子，最暴力的就是把状态设计得更细致一些。
例如，原本只设计：
表示前 个位置的最优答案。
但是后来发现，第 个位置选没选，会影响后面的选择。
那么就可以多加一个维度：
其中：
- 表示前 个位置处理完，并且第 个位置不选时的最优答案；
- 表示前 个位置处理完，并且第 个位置选择时的最优答案。
这样一来，状态点就从一类变成了两类：
点变细之后，边也就更清楚了。
所以，动态规划的状态并不一定是一开始就能完美设计出来的。很多时候，我们是在尝试写转移的过程中，发现信息不够，然后再反过来修改状态。
可以总结成一句话（这句对于很多动态规划有着醍醐灌顶的作用，用过都说好）：
转移缺什么，状态就补什么。
6. 按顺序求解
最后一步，就是按照正确的顺序计算所有状态。
因为动态规划是用小问题推出大问题，所以我们必须保证：
计算当前状态之前，它依赖的状态已经算完了。
例如， 依赖 和 ，那么我们就应该从小到大枚举 。
从状态图的角度看，这其实就是在按照图上的依赖关系求解。
如果把每个状态看成一个点，把转移看成一条有向边，那么我们要做的就是：
按照有向边的方向，把所有状态依次算出来。
这个顺序本质上就是一种拓扑顺序。
对于初学阶段，可以先简单理解成：
前面的状态先算，后面的状态再用前面的结果。
七、例题
下面通过几个经典例题，来对应前面讲过的几个概念。
第一题：走楼梯
假设一共有 级台阶，每次可以走 级或 级，问走到第 级台阶有多少种方法。
这是一道非常典型的计数型动态规划。
1. 状态是点
我们可以设计状态：
表示：
走到第 级台阶的方案数。
从图的角度看，每一级台阶都是一个点。
点 表示：
当前已经走到了第 级台阶。
2. 操作是边
每次可以走 级或 级，这也是我们能做的最小操作。
所以：
- 从第 级可以走 级到第 级；
- 从第 级可以走 级到第 级。
也就是图中有两条边：
这些边表示“走一步”的操作。
3. 转移是统计路径数量
因为题目问的是方案数，所以我们要求的是：
从起点走到点 的路径数量。
所有能走到点 的路径，都一定来自：
- 点 ；
- 点 。
所以：
这里的加法表示：
到达点 的路径数量，等于所有前驱点的路径数量之和。
4. 小结
走楼梯从状态图角度理解就是：
- 点：第 级台阶；
- 边：走 级或走 级；
- ：到达点 的路径数量；
- 目标：求到达点 的路径数量。
第二题：打家劫舍
假设有一排房子，每个房子里有一些钱。小偷不能偷相邻的两个房子，问最多能偷多少钱。
这是一道典型的最优化动态规划。
这道题的关键限制是：
不能偷相邻的两个房子。
也就是说，当我们走到第 个房子时，能不能偷它，取决于前一个房子有没有被偷。
所以我们不能只把状态设计成“处理到第 个房子”，还需要记录当前这个房子是否被偷。
1. 状态是点
从图的角度来看，我们可以把每个状态看成一个点：
其中：
- 表示：处理完前 个房子，并且第 个房子不偷；
- 表示：处理完前 个房子，并且第 个房子偷。
对应到 DP 数组中就是：
其中：
- 表示到达状态 时，能够得到的最大金额；
- 表示到达状态 时，能够得到的最大金额。
这里之所以要拆成两个点，是因为：
第 个房子偷没偷，会影响后面的边怎么连。
如果只用一个点表示“处理到第 个房子”，我们就不知道第 个房子还能不能偷。
2. 操作是边
接下来考虑状态之间的边，也就是一步操作。
如果第 个房子不偷，那么第 个房子偷不偷都可以。
所以图中有两条边：
这两条边表示：
不管前一个房子偷没偷，我现在这个房子都可以选择不偷。
因为第 个房子不偷，所以金额不会增加。
如果第 个房子偷，那么第 个房子一定不能偷。
所以图中只有一条边：
这条边表示：
只有当前一个房子不偷时，我现在这个房子才能偷。
因为偷了第 个房子，所以金额会增加 。
3. 转移是求最大路径权值
现在我们把每条边看成一次选择。
- 选择“不偷第 个房子”，边权是 ；
- 选择“偷第 个房子”，边权是 。
那么这道题就变成了：
在状态图中，从左往右走，求能获得的最大路径权值。
如果走到 ，说明第 个房子不偷。
它可以从两个状态转移过来：
所以：
如果走到 ，说明第 个房子偷。
它只能从 转移过来：
所以：
4. 最终答案
处理完所有房子后，最后一个房子可以偷，也可以不偷。
所以答案是两个终点状态中的最大值：
5. 小结
打家劫舍从状态图角度理解就是：
- 点： 和 ；
- 边：表示第 个房子偷或不偷；
- 边权：偷则增加 ，不偷则增加 ；
- ：到达点 的最大收益；
- ：到达点 的最大收益；
- 目标：求所有终点状态中的最大路径权值。
这就是“状态细化”的思想：
当一个状态无法确定后续能走哪些边时，就要把状态拆得更细。
在本题中，转移时缺少的信息是“当前房子有没有被偷”，所以我们增加了一维状态来记录这个信息。
第三题：找零问题
假设有若干种硬币面值，每种硬币可以使用无限次。现在要凑出金额 ，问最少需要多少枚硬币。
这是一道最小值动态规划。
1. 状态是点
我们可以设计状态：
表示：
凑出金额 最少需要多少枚硬币。
从图的角度看，每一个金额都是一个点。
点 表示：
当前已经凑出了金额 。
2. 操作是边
每次我们可以选择一枚硬币。
假设这枚硬币的面值是 。
如果当前已经凑出了金额 ，再加入一枚面值为 的硬币，就可以凑出金额 。
所以图中有一条边：
这条边表示：
选择一枚面值为 的硬币。
因为使用了一枚硬币，所以这条边的边权是 。
3. 转移是求最短路径
由于题目问的是最少需要多少枚硬币，所以我们要求的是：
从金额 走到金额 的最短路径长度。
如果最后一枚硬币的面值是 ，那么它一定是从金额 转移到金额 。
因此：
这里的 表示：
又使用了一枚硬币。
这里的 表示：
在所有能够到达金额 的方式中，选择硬币数量最少的一种。
4. 小结
找零问题从状态图角度理解就是：
- 点：金额 ；
- 边：选择一枚硬币；
- 边权：每选一枚硬币，代价为 ；
- ：从金额 到金额 的最短路径长度；
- 目标：求从 到 的最短路径长度。
所以找零问题本质上就是：
在金额构成的状态图上，求到达目标金额的最小代价。
最后，感谢 先生的润色。
有帮助，赞一个