动态规划位列GESP 6级大纲，是算法领域的必修课。然而，一个有趣的现象是：许多程序员在工作中却鲜有耳闻。究其原因，是因为在日常开发中，我们很少会直接谈论“动态规划”这个抽象术语，取而代之的，是它那些名声在外的具体实现：例如，代码比对时的Myers差分算法，自然语言处理中的隐马尔可夫模型，它们的核心引擎都是动态规划。那么，这个无处不在却又深藏功与名的“动态规划”，究竟是什么？

（注：GESP 是由 CCF 推出的面向中小学生的编程能力认证考试，正逐渐受到越来越多家长的认可。本人基于多年培训经验，编写了《CCF GESP 直通车 —— C++精讲精练》系列丛书。）

1. 动态规划的概念

动态规划是1957年理查德·贝尔曼在Dynamic Programming一书中提出的一种表格处理方法，它将原问题分解为若干子问题，自底向上先求解最小的子问题，并把结果存储在表格中，在求解大的子问题时直接从表格中查询小的子问题的解，以避免重复计算，从而提高效率。

这里“动态”的意思，并不是指程序在运行时“动态”地改变结构或类型（如动态语言那样），而是体现在其核心思想——通过子问题的求解，最终得到原问题的解。

动态规划算法常用来求解最优化问题，尤其是带有多步决策的最优化问题。能用动态规划解决的问题具备以下3个要素。

（1）最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。也就是说一个问题的最优解只取决于其子问题的最优解。

（2）无后效性：将原问题分解为若干子问题，每个子问题的求解过程作为一个阶段，当前阶段的求解只与之前阶段有关，与之后阶段无关，即某阶段的状态一旦确定，就不受这个状态后续决策的影响。

（3）重叠子问题：求解过程中每次产生的子问题并不总是新问题，会有大量子问题重复。在遇到重复子问题时，只需在表格中查询，无须再次求解。该性质不是使用动规划解决问题的必要条件，但是凸显了动态规划的优势。

这段文字虽然不长，但并不那么容量理解，下面我们通过一个例子来说明。由数字组成的金字塔型图案如下图所示:

从塔底选择一个点往上走，每一步可以走到左上方的点，也可以走到右上方的点（两边的点只有一种走法），因而从塔底到塔顶结束有多条路径。比如，可以是6-4-1-3-7，也可以是5-7-1-8-7。现在要求路径上经过的数字的和的最大值。

为了叙述方便，我们把塔底称为第一层，往上依次为第二层、第三层，这样塔顶为第5层，或者直接说塔顶。

如果从塔底开始，那么有5个结点可以选择，选择哪一点才能保证到达塔顶时，经过的数字之和最大呢？不知道。所以我们从塔顶往下倒过来推算。要到达塔顶结点7，有两条路径：第四层的结点3和结点8。我们不知道应该选择哪个结点，但可以确定的是，如果从塔底走到结点3经过的数字之和最大，那么就选择结点3，反之就选择结点8。也就是说，到达塔顶结点7的最优解，取决于到达第四层的结点3和结点8的最优解。

那么，到达结点3和结点8的最优解应该怎么求呢？我们只需使用同样的方法，继续往下推算，直到第一层。这样就把原问题的求解转化成了求每个结点的最优解（子问题），而每个结点的最优解，只取决于它下面左右两个结点的最优解，与这两个结点的其他属性（如到达这两个结点的最小和等）无关。这就说明这个问题满足动态规划问题的第一个要素：最优子结构。

我们在求每个结点的最优解的时候，并不需要考虑它的上面一层到底选谁，也就是说，每个子问题的求解只与之前阶段（它下面的两个结点的选择）有关，与之后的阶段（它上面的结点选谁）无关。这满足动态规划问题的第二个要素：无后效性。

在求第三层中的结点8的最优解时，转化为求第二层的结点2和结点7的最优解，而在求第三层中的结点1的最优解时，转化为第二层的结点7和结点4的最优解。这里第二层结点7的最优解是重叠的，所以这个问题有很多重叠子问题。这就是动态规划问题的第三个要素。

所以，这个问题可以用动态规划的思路来求解。

2. 动态规划的解题模式

动态规划解题的一般模式如下。

（1）划分阶段：按照问题的时间或空间特征，将问题分为若干个阶段。这也是动态规划状态转移的顺序，所以在划分阶段时，要注意划分后的阶段一定要有序或者是可排序的，以保证各状态的无后效性。

（2）状态表示：将问题发展到各个阶段时所处于的各种情况用不同的状态表示出来，通常状态的表示可以设为问题最终结果的一般化表示，并将最优解进行递归定义。

（3）决策与状态转移方程：在对问题的处理中做出的每种选择性的行动称为决策，即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。根据上一阶段的状态和决策来导出本阶段的状态就是状态转移。通常做法是根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

（4）初始值：所有的状态需要一个初始值；给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件，这些终止条件或边界条件是初始值的一部分。

（5）答案：问题的求解目标。

我们把这个解题模式应用到数字金字塔的例子中，其中状态转移方程如下：

结点i的最优解 = max(i的左下角结点的最优解，i的右下角结点的最优解) + 结点i自身的数值

而第一层每个结点自身的数值，就是它们的最优解。据此我们计算出每个结点上的最优解，如下图所示：

最后得到到达塔顶的最大值为30，经过的结点从下往上依次为：5、7、8、3、7。

3. 与贪心算法的区别

在5级中我们学习了贪心算法。动态规划看起来有点像贪心算法，两者都是把原问题划分成若干子问题，通过求子问题的解来得到原问题的解。但是两者具有本质的区别，主要体现在：

• 动态规划是考虑所有子问题的解，然后选最优；
• 贪心算法是直接选当前最优，不回溯，不比较其他可能性。

单从这句话看，似乎贪心算法比动态规划简单。但问题是，使用贪心算法的前提是，待求解的问题必须具有“贪心选择性质”，即“局部最优一定能导致全局最优”。如果待求解的问题不具有这个性质，那么就不能使用贪心算法。

以上面的题目为例，使用动态规划求解时，先求出第一层每个结点的最优解，再求出第二层每个结点的最优解，依次往上，最后求出塔顶结点7的最优解。整个过程对每个结点的最优解都计算了一遍，最后才得到原问题的最优解。

如果使用贪心算法，那么第一层会选择结点6，但是最后的结果表明，第一层选6是错误的。即使想从塔顶倒过来选，也会选择第四层的结点8，结果也是错误的。

这是因为这个问题本身没有“局部最优能够导致全局最优”的性质，所以不能使用贪心算法。

4. 与分治算法的区别

我们在学习分治算法时提到，分治算法的基本思想也是将一个大问题分解为若干个规模较小的子问题，那么动态规划与分治算法有什么区别呢？

动态规划与分治算法的区别在于：

• 分治算法的子问题是没有重叠的，因而分治算法通常使用递归来实现，如二叉树的前序、中序、后序遍历，左右子树是没有重叠的，因而可以使用递归来实现；
• 动态规划的子问题是互相重叠的，因而不适合使用普通的递归来实现（通常使用递推，或者带记忆化的递归）。

对此，大家有什么看法呢？欢迎留言讨论。

本文为学漄乐码堂主撰写。如果您想要学到真正的知识，而不只是应试的技巧，欢迎留言跟我联系。