从递归看动态规划

前情提要最优问题的本质目标函数 最优组合的求解策略枚举递归斐波那契数列问题描述示例解题思路迭代递归 深入理解递归堆栈与递归的状态存储递归与回溯树形结构与深度优先搜索 暴力递归的问题性能问题可读性与调试问题 暴力递归的优化——剪枝从整个搜索策略上来调整从解空间图的角度做调整 总结与升华

前情提要

在上一篇文章（从贪心算法开始认识动态规划——硬币找零问题）里，我们已经学习了贪心算法的思想，并且发现贪心算法是一种使用局部最优思想解题的算法，即从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的速度去求得更好的解，当达到算法中的某一步不能再继续前进时，算法停止。

通过硬币找零问题，我们也发现了贪心算法本身的局限性：不能保证求得的最后解是最佳的

因此，我们需要从整体最优的角度来解决算法问题。

最优问题的本质

所谓最优化问题，就是指在某些约束条件下，决定可选择的变量应该取何值，使所选定的目标函数达到最优的问题。

从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。在数学里一切都是函数，现在我们先把这个问题用函数形式来表示。

目标函数

假定给出 y 元硬币，硬币面额是 5 元和 3 元，求出需要的最少硬币数量。所谓的最少硬币数量就是 5 元硬币和 3 元硬币的总数，假定 5 元硬币数量为 $x_0$​，3 元硬币数量为 $x_1$​，那么用函数表示就是：

$f(x_0,x_1)=x_0+x_1$​

这就是所谓的“目标函数”

但是这个函数现在是没有任何限制的，我们希望对此进行约束，使得 5 元硬币和 3 元硬币的面值综合为 y。为此我们需要给出一个约束：

$5x_0+3x_1=y$

这个时候我们的问题就变成了，当满足这个约束条件的时候，求解函数中的变量 $x_0$​ 和 $x_1$​，使得目标函数 $f(x_0,x_1)$ 的取值最小。如果用数学的描述方法来说的话，就是下面这样：

$argmin(x_0,x_1)\in S(x_0+x_1)$

这个就是我们常见的 argmin 表示方式。它的意思是：当$(x_0,x_1)$ 属于 S 这个集合的时候，希望知道 $x_0+x_1$​ 的最小值是多少。其中 S 集合的条件就是上面的约束。

所以最优化问题在我们生活中是非常普遍的，只不过大多数问题可能都像硬币找零问题这样看起来普普通通，概念其实是不难理解的。

回到硬币找零这个问题上。由于 $(x_0,x_1)$ 都是离散的值，因此所有满足上述约束的 $(x_0,x_1)$ 组合，就是我们最终所求的集合。

而这个最优化问题的本质就是：

从所有满足条件的组合 $(x_0,x_1)$ 中找出一个组合，使得 $x_0+x_1$​ 的值最小。

所以，你会发现在这种离散型的最优化问题中，本质就是从所有满足条件的组合（能够凑出 y 元的组合）中选择出使得我们的目标函数（所有硬币数量之和）最小的那个组合。而这个所谓满足条件的组合不就是 argmin 公式中的那个集合 S 吗？

因此，这种离散型的最优化问题就是去所有满足条件的组合里找出最优解的组合。

换句话说，局部最优就是在一定条件下的最优解，而整体最优就是我们真正希望得到的最优解。

那么，怎么去寻找最优解呢？

最优组合的求解策略

枚举

如果想得到最优组合，那么最简单直接的方法肯定就是枚举。

枚举就是直接求出所有满足条件的组合，然后看看这些组合是否能得到最大值或者最小值。

在硬币找零问题中，假设现在需要给出 25 元的硬币，有两种组合，分别是 (5, 0) 和 (2, 5)，也就是 5 个 5 元硬币，或者 2 个 5 元硬币加上 5 个 3 元硬币，那么硬币数量最小的组合肯定就是 (5, 0)。

所以最简单的方法就是找出所有满足条件的组合，也就是上面两个组合，然后去看这些组合中的最优解。枚举本身很简单，就是把所有组合都遍历一遍即可。

可现在问题就是，如何得到这些组合呢？

这就需要我们通过一些策略来生成所有满足条件的组合。而递归正是得到这些组合的方法。

递归

其实最优化问题使用递归来处理是非常清晰的，递归是搜索组合的一种非常直观的思路。

在动态规划中，几乎所有问题都需要被描述成递归的形式。

斐波那契数列

严格来说，斐波那契数列问题不是最优化问题，但它能很好地展示递归的概念。

先来看一下斐波那契数列的问题描述。

问题描述

斐波那契数通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和：

示例

示例 1： 输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1。 示例 2： 输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

解题思路

很多人在解算法面试问题的时候有一种倾向性，那就是使用迭代而非递归来求解问题。

先不说这样的倾向性正确与否，那么我们就按照这个偏好来解一下（即斐波那契数列的循环解法）。

迭代

def fibonacci(n): resolution = [0, 1] # 存放结果 if (n < 2): return resolution[n] # 分别代表第item个值，第item个值的前两个值，第item的值 item, num1, num2, fib = 1, 0, 1, 0 while (item < n): fib = num1 + num2 num1 = num2 num2 = fib item += 1 return fib def main(): result = fibonacci(4) print(result) if __name__ == "__main__": main()

这样的解法固然没错，但是它几乎脱离了题设的数学表达形式。

在这道题目中，出题者“刻意”地写出了求解斐波那契数列的函数表达式，这其中有没有什么别的含义或原因呢？

当然有了，这个函数表达式很好地反应出了计算机科学中常见的算法形式：递归。 下面，就让我们来看看斐波那契数列与递归之间的关系。

递归

事实上，斐波那契数列的数学形式就是递归的，通过代码你应该能很清楚地看出这一点：

def Fibonacci(n): if (n == 0 or n == 1): return n if (n > 1): return Fibonacci(n - 1) + Fibonacci(n - 2) def main(): result = Fibonacci(4) print(result) if __name__ == "__main__": main()

递归形式的求解几乎就是简单的把题设中的函数表达式照搬过来，因此从数学意义上讲，递归更直观，且易于理解。

深入理解递归

堆栈与递归的状态存储

在计算机中，实现递归必须建立在堆栈的基础上，这是因为每次递归调用的时候我们都需要把当前函数调用中的局部变量保存在某个特定的地方，等到函数返回的时候再把这些局部变量取出来。

而用于保存这些局部变量的地方也就是堆栈了。因此，递归可以不断保存当前求解状态并进入下一层次的求解，并在得到后续阶段的解之后，将当前求解状态恢复并与后续求解结果进行合并。

在硬币找零问题中，我们可以放心的在函数中用循环不断遍历，找出当前面值硬币的可能数量。而无需用其它方法来存储当前或之前的数据。得益于递归，我们通过堆栈实现了状态存储，这样的代码看起来简单、清晰明了。

递归与回溯

在求解最优化问题的时候，我们经常会用到回溯这个策略。

上一篇文章里，我们已经提到过回溯的思想。在硬币找零这个问题里，具体说就是如果遇到已经无法求解的组合，那么我们就往回退一步，修改上一个面值的硬币数量，然后再尝试新的组合。

递归这种形式，正是赋予了回溯这种可以回退一步的能力：它通过堆栈保存了上一步的当前状态。

因此，如果想要用回溯的策略来解决问题，那么递归应该是你的首选方法。所以说，回溯在最优化问题中有多么重要，递归也就有多么重要。

树形结构与深度优先搜索

为了理解递归，这里用树来描述递归的求解过程：

你可以从中看到形象的递归求解过程：

每个节点的 /（斜线）左边表示当前节点使用的硬币面值，右边表示使用面值后的余额。蓝色节点就表示我们目前得到的解。

递归的过程的确就是一个树形结构，而递归也就是一个深度优先搜索的过程，先找到下一步的解，然后再回退，如此往复。

所以我们可以这样理解递归：作为一个算法解决方案，它采用了深度优先搜索的策略，去搜索所有可能的组合，并得到最优解的最优化问题。

如果在每个节点上加上当前这个节点求得的组合结果，就可以用递归树表示求解的组合空间：

从上图中我们可以发现，每个节点都存储了一个当前求解过程中的组合，和后续节点的组合合并到一起形成完整的答案。

而真正的求解组合，就是把所有余额为 0 的组合拿出来，经过去重之后得到的结果。

所以，你可以看到求解的组合就蕴含在这个递归的树形结算的节点空间中，这也就是为什么递归策略是行之有效的：我们可以通过穷举法从所有的解中得到最优解！

暴力递归的问题

虽然递归能解决问题，但是这样的穷举法效率实在低下，不仅如此，这样的代码可读性低且调试困难。

性能问题

暴力递归的最主要的特点就是穷举（暴力，你说是不是）。

如果我们只使用朴素的递归思路解题，就需要通过递归来暴力穷举出所有的组合，而且我们穷举的不只是组合，还是所有可能得到目标组合的组成路径！

这个在上面的图中我们可以看到，同样是求解 (2, 5) 这个组合，图中有多少种路径？这还只是 25 元和两种面值的情况。如果求解的金额和面值数量增加，那么我们可以看到这个树会以非常难以置信的方式增长，那么带来的性能问题就是灾难性的。如果你仔细观察一下，就会发现这个树会随着总额的增加呈现指数形式的增长。对于这种事情，我们难以接受。

因此，递归只是让问题可以求解，但是如果数据规模过大的时候暴力递归会引发极大的性能问题。

可读性与调试问题

虽然递归在数学意义上非常直观，但是如果问题过于复杂，一般是无法直接画出上面我画的那棵求解树的。

画求解树的时候，我们可以想出我们的求解过程是怎么进行的，但如果求解树的分支极多，那么很多人就很难继续在脑海中模拟出整个求解过程了。

因此，一旦程序出现 bug，当你想尝试去调试的时候，就会发现这样的代码几乎没有调试的可能性。这种问题在数据规模很大的情况下尤为明显。

暴力递归的优化——剪枝

从前面的图中看到，这棵树中有很多分支是完全相同的，从理论上讲最终只有两个组合，但是这棵树到达同一种组合的路径却非常多，所以优化递归的思路其实就是如何减少搜索的分支数量。

分支数量减少了，递归效率也就高了，这就是所谓的剪枝优化。

从整个搜索策略上来调整

第一种思路是仿照贪心算法，从整个搜索策略上来调整。也就是说，你要考虑这个问题的性质，即面值大的硬币用得足够多，那么这个组合的硬币总数肯定就最小。

所以在每一次递归时，我们不应该暴力地搜索所有的面值，而应该从面值最大的硬币着手，不断尝试大面值硬币的最大情况。如果无法满足条件再减少一个，再递归搜索。最后的代码就跟上一篇文章中的回溯代码一样，即通过贪心这种思路结合递归实现一种组合搜索。

殊途同归！从递归的角度重新解释了这个算法问题，而且代码实现也是一样的。

从解空间图的角度做调整

在解空间的图中，只要是余额相同的情况下，后面的搜索路径是完全一致的：

在图中圈出的两个部分就是重复的搜索路径。因为余额都是 12 元，所以后续的求解路径和结果完全相同。

在这个硬币求解问题中，当余额相同的时候，最优解是确定的。那么，如果能够避免相同余额下的重复搜索过程，那么算法执行速度是不是可以加快了？这就是重叠子问题。

你可以把求解 12 元的硬币数量理解成求解 25 元的硬币数量的一个子问题。在求解 25 元硬币过程中，会有很多种情况都要求解 12 元硬币的最优解。这类会出现重复求解的子问题称之为重叠子问题。

总结与升华

贪心算法只能解决局部最优问题，而我们的最终目标是解决整体最优问题（即最优解）。

自然地，枚举是获得最优解的理想方法。而递归可以帮助我们获得所有可能答案的组合。递归形式的求解几乎就是简单地把题设中的函数表达式照搬过来，它相较于迭代来说更直观，且易于理解。

但暴力递归有着十分明显的缺陷，它存在性能低下、可读性低和调试困难等问题。为此，我们可以进行剪枝：

利用预设条件减少搜索路径，优化最优组合搜索方案（硬币的优化）；利用重叠子问题，避免重叠子问题的计算。