前言

第一篇关于计算机的文章，打算来讲讲动态规划。

动态规划可以说是计算机科学中的一个重要算法，所有学习计算机的人无法绕过去。这个算法有些复杂，也比较反直觉，所以学习起来有一定难度。

我在本科时期第一次接触这个算法，能用动态规划解决一些作业题，但是始终没习得动态规划算法要领。参加工作之后，越发觉得算法对于计算机工程师十分重要，于是在工作多年以后，重新复习了各种各样的算法，有了新的理解。

先从两种思维模式讲起：递推和递归。

1 递推和递归的思维模式

“动态规划”字面给人一种高深莫测的感觉。其实原理并不复杂，只是这种算法解决问题的方法不符合我们的日常生活的直觉。

1.1 自下而上的递推：生活中的直觉

我们在日常生活中是怎么处理一件事的？举个例子，如果我们打算准备一顿4人份的晚餐需要买菜。该怎么办？

最符合直觉的方法，我们先盘算自己会做哪些菜肴，例如番茄炒蛋，红烧狮子头，酸汤肥牛（我最喜欢肥牛！）啊，已经3个菜了，然后想想4人用餐，3个菜明显不够吃，于是我们拼拼凑凑，又加了2个不太拿手的菜。于是又想，万一做出了黑暗料理怎么办？思前想后，最后又点了两个外卖。一顿晚餐拼拼凑凑总算是搭配好了！

以上就是我们最直观的思考方式，也叫做自下而上的方法，数学上称为递推。先设定好一个大目标，然后用细节一步一步填充，直到细节拼凑的差不多了，最终目标也就完成了。

但是，这样的方法只能适用于一家四口人吃饭，如果面对100人的宴会用这种方法就只能抓耳挠腮了。

1.2 自上而下的递归：计算机的方法

但是计算机的思考方式和我们不一样。因为它的计算能力和记忆力都很强，所以它可以“自上而下”地处理问题。

回到晚餐的例子，假设是一个机器人来准备晚餐，它也许会这么做：

先看看有几个人，嗯，一共四个人，2男2女，设计6个菜，3荤2素1个点心，已经很丰盛了。然后对菜系分类，海鲜一道，鸡肉一道，鱼肉一道，豆制品一道，蔬菜一道，点心一道。然后，用菜谱数据库做匹配，菜谱就完成了：清炒蛤蜊，红烧鸡翅，清蒸桂鱼，麻婆豆腐，清炒菠菜，小笼包。根据菜谱采购食材，很容易了吧。

这就是计算机自上而下的思考方式，数学上称为递归。只要人数确定，菜谱数据库足够大，即使是 100 人的宴会也能轻松解决。

动态规划就是这样的思维，我们觉得它抽象，是因为与我们惯用的思维方式差别比较大。

2 钢筋切割问题

举个例子，“钢筋切割问题”：

假设市场上不同长度的钢筋价格不一样（价格并非与长度等比例相关），现在有一家卖钢筋的公司能找到特定长度钢筋的货源，并且能不费吹灰之力将钢筋切割开来销售，那么如何切割钢筋才能将出售的价格最大化？

现在有一个不同长度钢筋的价目表：

长度（米）	1	2	3	4	5	6	7	8	9	10
价格（元）	1	5	8	9	10	17	17	20	24	30

假设现在有一个 4 米长的钢筋，如何切割才能让这条钢筋卖最多的钱？

这个问题无法一眼看出来答案，最简单直观的办法就是穷尽所有的切割方式，然后找出总价最高的那个：

完全不切割，价格 9 元
全部切割成1米，价格 4 元
按照3+1方式来切割，价格 8+1=9 元
按照2+2切割，价格 5+5=10 元
按照1+1+2切割，价格 1+1+5=7 元

穷尽了以上所有的可能性之后，我们得到答案：按照 2+2 方法切割，卖出的价格最高10元。

但是，用这个穷举的方法总是显得不那么聪明。

首先，对于示例中4米的钢筋，如果考虑 3+1 和 1+3 是两种不同的切割方案，那我们就必须穷举 $2^3=8$ 次才能找到最优解。再者，如果这根钢筋不是4米而是10米，那我们必须穷举 $2^9=512$ 次。如果钢筋的长度再长，就形成了指数爆炸，我们就很难用穷举来解决这个问题了。

那有没有更加聪明的办法呢？

3 动态规划算法

当然有，那就是动态规划算法！

动态规划（Dynamic Programming）中的“规划”（Programming）实际上是“填表”，而非“编程”的意思。

仔细观察，我们发现，一定长度的钢筋总是存在一个最优的切割方案，例如：

长度 1 ：不切割，价格为 1
长度 2 ：不切割，价格为 5
长度 3 ：不切割，价格为 8
长度 4 ： 2+2，价格为 10
长度 5 ： 2+3，价格为 13

得到结果后，我们发现一个洞见：计算更长钢筋的切割方案时，可借鉴已经计算好的结果，例如计算5米钢筋的切割方案时，可以参考长度为1、2、3、4米钢筋已经找到的最优切割方案，然后计算5米的最优方案，避免了重复计算。

以上的洞见可以总结为“钢筋切割问题”的两个特征：

最优子结构：一个问题的最优解由几个相关的子问题的最优解组合而成。
- 解释：例子里就是5米钢筋可以直接使用1、2、3、4米的最优解。
- 启发：这样我们就可以使用递归方法找到问题和子问题之间的关系，进而用一个递推式来求解。
重叠子问题：子问题的数量是有限的，会在计算过程中被重复计算。
- 解释：例如5米钢筋需要找1、2、3、4米的最优解，4米钢筋找1、2、3米钢筋的最优解，以此类推。最终的结果就是，1米钢筋的最优解会被计算很多次，因为所有长度的钢筋都要用它的最优解。
- 启发：我们可以将更短长度钢筋的解保存下来，避免重复计算，提高计算效率。

3.1 状态转移方程

因为后面的步骤可以借鉴前面步骤的结果，我们可以找到长度 n 和长度 n-1, n-2, .... , 2, 1 之间的关系，推导出公式：

r_n = \max(p_n, r_1 + r_{n-1} , r_2+r_{n-2}, \cdots, r_{n-1}+ r_1)

$r_n$ 表示长度为 n 钢筋切割方案的最优解
$p_n$ 表示长度为 n 钢筋的售价

如何理解这个公式，很简单：长度为 n 钢筋的价格最优解是结合前面步骤结果，然后找所有可能方案中的最大值，这些方案包含以下两种情况：

完全不切割，公式中体现为 $p_n$
对钢筋分为两个部分的情况。公式中体现为 max()中除了 $p_n$ $p_{n}$ 的其余的部分。
- 例如长度4可以分为 3+1 , 2+2 , 3+1 三种情况，然后找这几个方案的哪个是最优的。
- 有同学会问 1+1+2 和 1+1+1+1 在哪里？其实已经包含在 1+3 和 2+2 中了，算法会在后续的过程中步骤中考虑更细拆分的情况。

举个例子，长度 4 的钢筋，第一步的状态转移方程为：

$r_4 = \max(p_4, r_1+r_3, r_2+r_2, r_3+r_1)$

然后 $r_3 , r_2$ 可以按照相同的公式进一步拆分。

为了进一步理解，我们可以将这个方程看作是数学上的“递推式”，即为“从上一步推下一步的方程”。递推式的证明一般要使用数学归纳法。【注意，数学上虽然这里叫“递推式”，但使用的思想其实是“递归”】

实际上，例子中“状态”可以解释为“长度为n时最大化出售价格的切割方案”。根据状态转移方程，我们可以得到一个表示为树的计算过程：

每一个圆点都是一个“状态”，状态转移方程描述了不同状态之间的递归关系，所以它非常重要！另外从图中也能看出部分计算状态是重复的（出现了重复的0、1、2），这就是“重叠子问题”的特征。

从图中可以看出，我们从状态 4 出发，一步一步用状态转移方程拆分成子状态，来解决问题。这也是“自上而下”思维的体现。

有了状态转移方程之后，我们就可以轻而易举的编程了，不过在编程时，要注意必须把最优解对应的最优方案（重叠子问题）保存下来，供后面的计算使用，如果仅仅用代码实现状态转移方程，程序会递归执行重复的计算，浪费计算时间（也叫“备忘”机制）。【现在，你知道为什么“规划”是“填表”了吧，其实就是把中间过程都记录下来！】

4 总结

计算机和人类思维不同，计算机善于用自上而下的递归解决问题，而最符合人类思维的方法是自下而上的递推。

动态规划算法就是一个“自上向下”的方法，它使用递归的方式解决复杂的问题，并把算法的复杂性控制在合理的范围内。

通过这个问题，我们看到，问题的规模不同往往会导致解决方案在质上的变化。例如在钢筋切割问题中，钢筋短的情况下我们可以用穷举来解决问题，但是钢筋一旦更长，我们就很难用原来的方法解决问题了，而应该使用更“聪明”的方式解决。也就是计算机能够施展拳脚的地方。

参考

本文中的例子出自于：《算法导论（原书第三版）》 15章：动态规划
递归和递推以及动态规划的基本概念：吴军，《计算之魂》 5.4 动态规划算法
苗华栋，在知乎上的回答：https://www.zhihu.com/question/23995189/answer/1160796300
捡田螺的男孩，在掘金上的文章：https://juejin.cn/post/6951922898638471181