不是我催... 以后大家学动态规划，都得要看这个视频。

UP主: NotOnlySuccess · 时长: 19:57 · 🔗 B站原视频

标签: 动态规划 · 算法 · 编程开发 · 计算机基础 · 面试算法

从数字三角形引入动态规划

有这么一个数字魔塔，我们位于塔顶，每次移动可以选择向下走，到左右两个相邻的位置。现在需要找一条路径到达塔底，使得路径上所有数字之和最大。

先来看朴素的做法，就是将所有可行的路径都枚举出来。那总共有多少路径呢？每次往下有两种方式，假设塔高是 N，我们一共要往下走 N-1 层，所以总共有 2 的 N-1 次方个方案。如果 N 是 30，就已经是天文数字了，更别说一百、一千。

那更高效的解法是什么呢？这个视频我们通过 1994 年国际信息学奥林匹克竞赛世界总决赛的经典题目——数字三角形，带大家系统性了解算法设计中极其重要的分支：动态规划。

什么是动态规划？

我们先来看动态规划的三大要素：最优子结构，巴拉巴拉巴拉；无后效性，巴拉巴拉巴拉；重叠子问题，巴拉巴拉巴拉。

对初学者来说，这段内容一定是看不懂的。如果有谁尝试根据定义去学习，那简直就是从入门到放弃。大家可以暂停尝试理解，反正我初见时的感受是每个字都认识，但连起来就不知道是什么意思。因为定义和教学的目的不同，定义讲究的是科学严谨，需要用没有二义性的语言来描述，这就会有非常多晦涩难懂的词和概念，所以并不适合初学者。只有在自己不断练习摸索之后，再回来看这三句话，才会有感悟，才能体会到这三句话的精髓。

那接下去我用初学者甚至外行都能理解的一句话来描述什么是动态规划：从初始点出发，经过一系列的行进路线到达终点，求问题的最优值、方案数或概率的算法，就是动态规划。

在这个基础上，我们再稍微修饰一下，以适用于更普遍的情况：从初始状态出发，经过一系列的状态转移，到达目标状态。是不是和搜索最短路有点像？没错，很多算法从本质上来说，都是围绕着状态和状态转移这两个概念展开的。

数塔问题的动态规划求解与复杂度

当然，动态规划在这个基础上还有两个限定条件：状态转移必须是有方向的，并且整个图不能成环；状态的个数需要在可接受的范围内。对限定条件有困惑的同学不要着急，后文会进行详细解释。

我们先回来看开头的数塔问题，它完全符合这个特征。从最高处的起点出发到最低处的终点，可以有多个终点，当然也可以有多个起点。方向是从上到下，不能从下到上，保证了不会成环。点的数量，或者说状态的数量，就是等差数列求和，有 (1+N)*N/2 个。

这个问题符合了动态规划的描述，那应该如何求解呢？比如我们现在需要计算起点到红色点的最大路径，假设我们已经计算出来红色点前置的所有点，也就是这两个蓝色点的最大路径。那么红色点的最大路径，一定就是这两个蓝色点的值取最大值，加上当前位置的数字。也就是说，我们不需要关心蓝色点是怎么从起点出发到达它的轨迹，只需要记录起点到达它的最大值。这样就将多种可能性浓缩到了一个状态中，在计算后续的状态时，就可以直接拿来使用。进行一次最大值和加法，就可以计算出一个状态。

大家可能会想到用空间换时间，没错，动态规划就是一种用空间换时间的算法。因此我们只需要从上往下、从左往右遍历每个状态，依次进行计算。因为有方向，所以当我们计算第 I 层时，第 I-1 层的各个点一定已经被计算好了。第一层的最大路径也就是从起点到起点，结果就是它自身。其他层的最大路径，只需要看有哪些点可以到它，可能是一个，可能是两个，取它们的最大值加上当前值，就是当前点的最大路径。

总共有 (1+N)*N/2 个点，记作 O(N²)；每次状态需要一次比较和加法，记作 O(1)。那么时间复杂度就是 O(N²)，完美解决。觉得头脑中产生风暴的同学可以回看一下，或者暂停在纸上进行模拟。

核心概念：状态与局面

有了这道题的铺垫，接下来我们进一步深入，来了解什么是状态以及状态转移。之前我们说的点、走，都是非常不形式化的表达。对于这个最简单的问题很好理解，但一旦问题变得复杂，用通俗化的语言来表达就会产生歧义。而状态和状态转移，就是用形式化的语言来描述问题。并且不仅仅是动态规划，像搜索、回溯、博弈、各类自动机以及更多高深的算法，都可以基于这两个概念进行更深层次的理解。

我们先来看什么是状态。很多教程会将它描述为子问题、阶段，没有错，但是比较抽象。为了初学者更好理解，我尝试用更具象化的方式来描述：状态是可以精确用数字描述的一个局面，以及所对应问题的值。

比如这个数塔问题，我们可以用“从上往下第 I 行”、“从左往右第 J 个”这两个数字来描述局面，比如第三行第二个。然后这个局面所对应的值，就是从初始局面（也就是起点）到这个局面的最大值。可以记作函数形式 F(I,J)，也可以记作数组形式 DP[I][J]。DP 是动态规划英文 Dynamic Programming 的缩写，一般作为数组名。这两个形式代表的都是状态，也就是 (I,J) 这个局面的值。

有了这种形式化的表达，原本口语化的描述“一个点可以到下一层左边和右边的点”，就可以用更精准的数学语言来描述：(I,J) 可以到 (I+1,J)，也可以到 (I+1,J+1)；或者反过来，(I,J) 可以由 (I-1,J-1) 和 (I-1,J) 到达。

接着我们再用几个大家熟知的游戏，来更深入地阐述什么是局面和状态。

比如飞行棋，四个选手轮流行动，一共有 16 架飞机。因此我们可以用一个 0~3 的数字表示当前是谁的回合，16 个数字表示对应飞机所在的位置，算上停机坪一共有 81 个格子。那么这 17 个数字，就可以精准描述某个特定的局面。

再比如五子棋，15×15 的格子摆下黑白两色棋子。我们一样可以用一组数字来记录位置，如果不需要关注落子顺序，也可以单纯地记录 225 个位置分别是什么状况：空位置即为 0，白子即为 1，黑子即为 2。这样就可以通过 225 个数字描述特定的局面，也可以将这 225 个数字压缩成一个巨大的三进制整数。

再比如魔方，一共有 6 个面，54 个小面，每个面可能会有六种颜色，所以我们可以用 54 个数字来描述某个局面。

这里举了三个例子，虽然局面的描述很复杂，不过应该都很好理解。但刚刚的描述都还不是状态，因为没有赋予它们问题，这个局面也就只是一个局面，没有对应的值。我们可以赋予对应的问题，比如对于某个飞行棋的局面，某个玩家赢的概率是多少？对于某个五子棋的局面，黑方是否必胜？对于某个魔方的局面，还原的最小步数是多少？这样它们就成了状态。

当然这些都是属于比较难的问题，在新手村直接搬出大 boss 的原因，是为了让大家更好地理解什么是局面、什么是状态。新手在学习动态规划时，有一大部分同学都会很吃力，原因就是对状态没有深刻的理解。其实大部分动态规划的问题，只需要将状态找出来，问题基本上就迎刃而解了。因此我用三个非常复杂但又非常好理解的例子，来加深大家对状态的理解，可以暂停消化一下。

核心概念：状态转移与决策

接着我们再来说状态转移。有了上述理解后就比较简单了，就是从一个状态，在问题的约束下转移到另一个状态，同时伴随着值的变化。这个过程可以用一个词来概括，就是决策。动态规划说白了，其实就是站在全局视角思考最好的决策，使得最终方案最优的一个方法。

我们来具象化看看什么是决策。比如数塔问题，对于状态 (I,J)，可以到 (I+1,J) 和 (I+1,J+1)，但不能反过来到 (I-1,J)，也不能直接跳到 (I+2,J)，同样不能直接到 (I+1,J+2)。这就叫约束，或者叫规则。我们的决策必须在符合问题约束的前提下进行。

但光知道怎么转移还不够，我们还需要计算转移的过程中（或者决策的过程中）值发生了哪些变化，或者说转移的开销成本，这样才能构成完整的状态转移。通常我们会将开销称作权重（Weight），用 W 来表示，或者用 Cost (C) 来表示。比如 F(I,J) 加上目标点的值 W(I+1,J)，可以转移到 F(I+1,J)；也可以加上 W(I+1,J+1)，转移到 F(I+1,J+1)。

接着我们对三个大 boss 进行进一步的剖析，更深入地了解状态转移。

飞行棋每次可能掷出 1~6 个点数，然后选择四架飞机中的其中一架进行移动。假设飞机都能移动并且选择是随机的，那么当前状态就有 1/24 的概率转移到后续的 24 个状态。换句话说，转移的开销就是 1/24。因为算的是概率，所以是当前状态概率乘以开销，累加到下一个状态。

再来说五子棋，我们的决策很直白，可以在任意空白位置落子，然后转移到下一个状态。决策非常多，空白局面时有 225 种状态转移的方式。那如何确定某个状态的胜负性呢？这就需要用到博弈论中的初阶知识：一个状态如果可以到必败态，那么它一定是必胜态；如果一个状态只能到必胜态，那么它只能是必败态。用大白话来讲，就是只要一个决策可以导致你必败，那我一定必胜；如果所有决策都会导致你必胜，那我一定必败。很直白，很好理解。通过这个知识加上状态转移，只要计算量足够大，我们就可以把所有状态的胜负性求出来。顺带说一句，没有特殊约束规则的五子棋，先手必胜。

再来看魔方，我们将旋转按 X、Y、Z 三轴拆解，可以选择两边按顺时针、逆时针方向旋转，也就是说一共有 12 个状态转移方式。我们求的是最少步数还原，所以每次转移的开销就是 1 步。对于这种转移的权重是 1 的问题，我们已经学过，可以用广度优先搜索算法来解决。

以上这三个问题并非都是动态规划，但可以让大家更好地理解状态以及状态转移这两个核心概念。因此上文也提到，状态和状态转移并非动态规划的专属概念，对它们深刻理解后，很多算法都可以有不一样的体悟。可以休息片刻。

动态规划的前提：无后效性与有向无环图（DAG）

接着我们来说动态规划的一个重要概念：无后效性。也就是上文提到的限制条件：转移必须是有向，并且整体不能成环，简称有向无环图（DAG）。这是动态规划成立的前提条件。

无后效性和有向无环图在动态规划的问题上其实可以划等号，只是从不同视角出发看待问题。无后效性的概念会更抽象一些，对初学者不够友好，因此我们从更具象化的有向无环图来解释。

让我们在数塔问题上稍稍做些修改，增加一个传送门，在某个点时可以选择传送到另一个位置。这样我们还能找到一条从塔顶到塔底的最长路径吗？找不到了。因为在这三个节点之间可以无限循环，原因是状态转移成环了。用通俗的话来说，就是当我要计算一个状态时，它的前置状态还需要等待当前状态的结果才能计算，形成了循环依赖，因此无法求解。这其实就是后效性。

我们现在再来正式看看无后效性的定义：将原问题分解成若干个子问题，每个子问题的求解过程作为一个阶段。当前阶段的求解只与之前的阶段有关，与之后阶段无关。即某阶段的状态一旦确定，就不受这个状态后续决策的影响。

是不是比最开始看到这段话更有感觉了一些？虽然表述不同，但和有向无环图其实是同一个意思。

我们再将这个图修改一下，现在是否可以用动态规划来求解呢？可以，因为它没有成环。不过我们在枚举状态的计算顺序时得要特别注意，需要保障每个状态在计算时，它的前置状态必须已经被计算出来了。对于这个图，我们就可以从左往右一列一列枚举，来保障无后效性。对于更加复杂的有向无环图，线性循环枚举无法保证无后效性，就需要用到额外的技巧，如广度、深度优先遍历来保障枚举的顺序，在后文也会介绍。

因此我们不难得出动态规划成立的前提条件：需要符合无后效性，等价于状态和状态转移所构成的图是有向无环图，等价于我们编写代码时，枚举状态的计算顺序需要保障可以转移到当前状态的前置状态都已经被计算出来了。这就是动态规划的底层逻辑。在往后的动态规划学习中，不妨多回过头来看看这个逻辑。

动态规划的复杂度与难点

接着我们再来说最后一个知识点。动态规划的复杂度非常简单，就是状态数量乘以每个状态计算所需要的开销，也就是转移的开销。比如有 N² 个状态，每个状态计算需要 N 次转移，那复杂度就是 N 的三次方。

所以如果想优化动态规划的复杂度，方向就是设计更小、更合理的状态，或者降低转移的开销。这也是视频开头在介绍动态规划定义时加了一个限制条件：状态的个数需要在可接受的范围内。如果状态数过大，也就意味着复杂度过大。

而动态规划的难度其实也取决于这两个维度。对于简单的动态规划，状态设计较为直白，状态设计出来之后，转移自然而然就浮出水面了。对于正常难度的动态规划，难点是如何设计状态，不过大部分都有套路，所以需要学习各种不同特征的动态规划模型，学习之后就可以公式化思考。对于难的动态规划，就需要用到一些特殊性质或数据结构来优化转移的开销，这也算是一种高级的套路。

而我认为最难的动态规划，需要将原本杂乱无章的状态，通过复杂的证明梳理成可接受的状态，这种基本上就是神仙题了。比如 2020 年 World Finals 的夺冠题 Bridging the Gap，感兴趣的同学可以去了解一下。这些具备特征的模型以及优化手段，在后续的课程中都会逐步展开。

状态转移方程的标准写法

好啦，动态规划理论说完了，大家可以休息片刻消化一下。接着我们来看具体的实操。

先来看状态转移方程。之前我们在讨论数塔的状态转移时，其实列过两个类似方程的式子。虽然已经可以表达如何转移，但这种表示还不够形式化，所以需要一套明确的标准，谁来编写都一样，谁来看都能看得懂，这就是状态转移方程的作用。

比如这次数塔问题的状态转移方程，我们来看看如何理解。分成四部分：状态的表示、初始状态、计算的条件、计算的方式。

等号左边代表如何表示状态，就如上文提到，用 I 和 J 来表示第几行、第几个，然后用函数的形式表示它的值。等号右边代表各种情况下的计算方式，分为左右两部分。右半部分是条件不同的状态，因为边界情况可能会有不同的计算方式，所以需要进行分类。左半部分就是具体的计算方式，可以理解为当符合右半部分条件时，用左半部分的公式来计算。

第一行，也就是第一个分类，往往是初始状态，即不需要计算就可以得到答案的状态。I 等于 0，也就是位于塔顶的状态，它就等于塔顶的值。接下来就是对各种边界情况的分类讨论。这就是状态转移方程。

当然有时候也可以简写，忽略初始状态和边界情况的讨论，只写一般情况。相比于完整的公式，虽然少了点严谨性，但更简洁。

编写动态规划代码的四种方式

最后我们进入本节课的最后一趴：如何编写代码。我总结了四种编写方式，分别是逆推、顺推、记忆化搜索、拓扑搜索。我们以数塔为例逐一说明。

逆推的意思是当前状态从哪来，哪些状态能到它。我们开一个用于记录状态的数组，和状态数一一对应，一般直接用 DP 或者 F 作为数组名。然后按照符合无后效性的顺序，枚举要计算的状态。接着套用状态转移方程就可以解答，输出最后一行（也就是所有目标状态）的最大值即可。

再来看顺推。顺推的意思是当前状态到哪去，可以转移到哪些状态。依然也是按照符合无后效性的顺序来枚举，不过在计算时，我们需要先计算这个状态往后转移的结果，将其记录到下一个状态中。这样写起来会比逆推更简单，并且正向思考也会更加自然而然。这个写法需要有三个注意点：

1. 需要将初始状态单拎出来。
2. 不需要遍历目标状态，因为它不会往后发生转移。
3. 需要将所有状态设置一个初始值，根据题目要求可能是 0，可能是极大值或极小值，方便我们在计算的过程中直接进行更新。

这两种都是动态规划的基础写法。有的题用顺推写会更方便，有的题则更适合逆推。

再来看记忆化搜索。很多教程会将记忆化搜索误称为算法，或者将它归为搜索，其实它只是动态规划的一种实现方式。编写步骤如下： 将所有状态设置为一个在答案域中不会出现的值，比如 -1。然后枚举目标状态，开始深度优先搜索。深搜的参数就是局面的表示 I 和 J，过程就是用逆推的方式计算，也就是从哪来。编写递归函数时，先判断当前状态是否等于 -1。如果不等于 -1，那么就代表已经被计算过了，不需要重复计算，直接返回结果即可。否则我们就根据状态转移方程计算这个状态，并将它记忆化起来，下次再搜到这个状态时就可以直接返回了，因此叫记忆化搜索。这里我用引用 Result 来表示状态 (I,J)，编写起来会更加方便。 记忆化搜索的一个好处是，不需要关心无后效性的顺序，深度优先搜索天然具备这个能力。对于一些无后效性顺序并不好用 for 循环枚举的问题，就可以采用记忆化搜索。

最后再来说下拓扑搜索。它和记忆化搜索类似，也适用于无后效性顺序不好用 for 循环枚举的问题。记忆化搜索过程采用的是逆推（这个状态从何而来），而拓扑搜索采用的是顺推（这个状态可以去往何方）。对于有些问题，顺推其实要比逆推更容易编写。 在编写拓扑搜索时和上面几个写法不同，我们需要先进行一些准备工作。对于每个状态，处理出有多少状态能转移到它，记录到入度（In-degree）数组中。接着开一个队列，先将初始状态加入队列，并计算它的值。很容易可以想见，初始状态的入度一定是 0，因为没有其他状态可以到它。 然后才开始动态规划编写。使用广度优先搜索，弹出队头作为当前状态 A，然后计算所有可到达的状态 B。在计算 B 时，顺带将 B 的入度减一，代表 B 的其中一个前置状态 A 转移到它的步骤已经计算好了。当 B 的入度变成 0 时，就代表所有的前置状态都已经计算完，也就是 B 这个状态已经 Ready，此时可以入队进行后续的转移。当广度优先搜索结束时，所有的状态就被计算出来了。 和顺推的思路其实一样，注意点也相同：初始状态需要单拎出来；不需要遍历目标状态；需要将所有的状态设置为一个初始值。这种做法其实本质上是在做拓扑排序，按照无后效性的顺序进行每个状态的遍历，所以无后效性顺序其实也可以称之为拓扑序。 拓扑搜索的写法并不常见，甚至这个名字都是我现取的，写起来代码量也比较大，对于这题来说就是杀鸡用牛刀了。不过对于无后效性顺序不好枚举，用逆推的记忆化搜索来编写又比较难理清思路时，使用拓扑搜索往往会有奇效。

动态规划的模型分类与学习路线

当然除了这四种写法外，还有滚动数组、数组复用等优化空间的写法。这些都是小技巧，不作为写法、思想上的分类，在后续的课程中会在合适的时机进行介绍。

我的课程专注的是“道”，是思想上的分类，在此基础上辅以“术”，也就是技巧，这样学习才能事半功倍。整个课程的内容也是如此，先用大篇幅介绍动态规划的核心要素，而不是直接以一系列的经典动态规划路子告诉你应该怎么做，然后照着模仿学习。因为内功不扎实，直接学习招式只能领悟到一些皮毛，需要额外花费很多代价才能自我总结出一些精髓。

OK，以上就是动态规划概述的所有内容。虽然我们只分析了一道动态规划题，但展开深入介绍了动态规划的所有要素：局面、状态、状态转移、无后效性、DAG、复杂度、状态转移方程以及动态规划的四种写法。对于初次学习动态规划的同学，可以先有个大致印象，在后续课程介绍各个类别的动态规划时，我们会继续加深理解。对于已经有一定动态规划基础的同学，相信看完视频对动态规划的理解应该会更深刻一些。

最后我们来聊一下动态规划模型的分类。传统分类可能会将动态规划分为以下几类：线性 DP、背包 DP、二维 DP、区间 DP、DAG DP、树形 DP、数位 DP、状压 DP、动态 DP，难度依次递增。

在我的分类中略有不同。由于线性 DP 是最常见的 DP，所以我将它更细致地拆解成了前缀 DP、01 DP 和一般线性 DP，可以有更好的学习曲线。对于二维 DP，也并非传统意义上的开了二维数组，而是两个独立的状态进行叠加才是二维 DP，所以可能改成笛卡尔积 DP 会更为贴切。对于区间 DP，从区间这个表象往更深层次挖掘，我将它定义为划分 DP，就是一个状态并非从某个状态过来，而是划分成两个或多个状态共同推导而来。对于状压 DP 也做了更细致的划分，分为 TSP 旅行商 DP、一般状压 DP、轮廓线插头 DP，并增加了一个新的分类：斯坦纳树 DP。这是一个图论问题，但其实需要动态规划来解决。

在一些分类中还会有计数 DP、概率 DP，这两者其实只是计算值的类别不同，状态和状态转移并非新的模型，所以不列作模型的分类。如果硬要分，应该是让所求值的类别分为极值 DP、计数 DP、概率 DP，与 DP 模型是不同的维度。两个维度可以进行笛卡尔积，可以有求方案数的插头 DP，也可以有求概率的线性 DP。

在这门算法思想课程中，会细致地讲解前缀 DP、01 DP、一般线性 DP、背包 DP、笛卡尔积 DP、划分 DP、DAG DP，会以更具特征的方式来讲解最大子段和、最长递增子序列、最短编辑距离、最长公共子序列等经典问题，让大家有更深层次的理解，并辅以大量习题，做到从入门到进阶。

好了，本节课到此结束，让我们下节课前缀 DP 再见。