c 递归算法-看图话说「递归」与「动态规划」| 算法干货

在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。

程序员小吴打算使用动画的形式来帮助理解「递归」，然后通过「递归」的概念延伸至理解「动态规划」算法思想。

什么是递归

先下定义：递归算法是一种直接或者间接调用自身函数或者方法的算法。

通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：

递归动画

通过动画一个一个特点来进行分析。

1.一个问题的解可以分解为几个子问题的解

子问题就是相对与其前面的问题数据规模更小的问题。

在动图中①号问题（一块大区域）划分为②号问题，②号问题由两个子问题（两块中区域）组成。

2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

「①号划分为②号」与「②号划分为③号」的逻辑是一致的，求解思路是一样的。

3. 存在递归终止条件，即存在递归出口

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。

①号划分为②号，②号划分为③号，③号划分为④号，划分到④号的时候每个区域只有一个不能划分的问题，这就表明存在递归终止条件。

从递归的经典示例开始一.数组求和

数组求和

%ignoRe_pRe_1%

后面的 Sum 函数要解决的就是比前一个 Sum 更小的同一问题。

%ignoRe_pRe_2%

以此类推，直到对一个空数组求和，空数组和为 0 ，此时变成了最基本的问题。

%ignoRe_pRe_3%

二.汉诺塔问题

汉诺塔（Hanoi ToweR）问题也是一个经典的递归问题，该问题描述如下：

汉诺塔问题：古代有一个梵塔，塔内有三个座a、B、c，a座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这个盘子从a座移到c座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

两个盘子

三个盘子三.爬台阶问题

问题描述：

一个人爬楼梯，每次只能爬1个或2个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法？

先从简单的开始，以 4 个台阶为例，可以通过每次爬 1 个台阶爬完楼梯：

每次爬 1 个台阶

可以通过先爬 2 个台阶，剩下的每次爬 1 个台阶爬完楼梯

先爬 2 个台阶

在这里，可以思考一下：可以根据第一步的走法把所有走法分为两类：

所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 ，然后加上先走 2 阶后，n-2 个台阶的走法。

用公式表示就是：

f(n) = f(n-1)+f(n-2)

有了递推公式，递归代码基本上就完成了一半。那么接下来考虑递归终止条件。

当有一个台阶时，我们不需要再继续递归，就只有一种走法。

所以f(1)=1。

通过用n = 2，n = 3这样比较小的数试验一下后发现这个递归终止条件还不足够。

n = 2时，f(2) = f(1) + f(0)。如果递归终止条件只有一个f(1) = 1，那f(2)就无法求解，递归无法结束。

所以除了f(1) = 1这一个递归终止条件外，还要有f(0) = 1，表示走 0 个台阶有一种走法，从思维上以及动图上来看，这显得的有点不符合逻辑。所以为了便于理解，把f(2) = 2作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走。

总结如下：

递归终止条件

通过递归条件：

%ignoRe_pRe_4%

很容易推导出递归代码：

%ignoRe_pRe_5%

通过上述三个示例，总结一下如何写递归代码：

什么是动态规划

介绍动态规划之前先介绍一下分治策略（DIVide and conqueR）。

分治策略

将原问题分解为若干个规模较小但类似于原问题的子问题（DIVide），「递归」的求解这些子问题（conqueR），然后再合并这些子问题的解来建立原问题的解。

因为在求解大问题时，需要递归的求小问题，因此一般用「递归」的方法实现，即自顶向下。

动态规划（Dynamic PRogRamming）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。

区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。

其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。

即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

与「分治策略」「动态规划」概念接近的还有「贪心算法」「回溯算法」，由于篇幅限制，程序员小吴就不在这进行展开，在后续的文章中将分别详细的介绍「贪心算法」、「回溯算法」、「分治算法」，敬请关注：）

将「动态规划」的概念关键点抽离出来描述就是这样的：

从递归到动态规划

还是以爬台阶为例，如果以递归的方式解决的话，那么这种方法的时间复杂度为O(2^n)，具体的计算可以查看笔者之前的文章 《冰与火之歌：时间复杂度与空间复杂度》。

相同颜色代表着 爬台阶问题 在递归计算过程中重复计算的部分。

爬台阶的时间复杂度

通过图片可以发现一个现象，我们是 自顶向下 的进行递归运算，比如：f(n)是f(n-1)与f(n-2)相加，f(n-1)是f(n-2)与f(n-3)相加。

思考一下：如果反过来，采取自底向上，用迭代的方式进行推导会怎么样了？

下面通过表格来解释f(n)自底向上的求解过程。

台阶数123456789

走法数

表格的第一行代表了楼梯台阶的数目，第二行代表了若干台阶对应的走法数。

其中f(1) = 1和f(2) = 2是前面明确的结果。

第一次迭代，如果台阶数为 3 ，那么走法数为 3 ，通过f(3) = f(2) + f(1)得来。

台阶数123456789

走法数

第二次迭代，如果台阶数为 4 ，那么走法数为 5 ，通过f(4) = f(3) + f(2)得来。

台阶数123456789

走法数

由此可见，每一次迭代过程中，只需要保留之前的两个状态，就可以推到出新的状态。

show me the code

%ignoRe_pRe_6%

程序从i = 3开始迭代，一直到i = n结束。每一次迭代，都会计算出多一级台阶的走法数量。迭代过程中只需保留两个临时变量 a 和 b ，分别代表了上一次和上上次迭代的结果。为了便于理解，引入了temp变量。temp代表了当前迭代的结果值。

看一看出，事实上并没有增加太多的代码，只是简单的进行了优化，时间复杂度便就降为O(n)，而空间复杂度也变为O(1)，这，就是「动态规划」的强大！

详解动态规划

「动态规划」中包含三个重要的概念：

在「 爬台阶问题 」中

f(10) = f(9) + f(8)是【最优子结构】

f(1) 与 f(2)是【边界】

f(n) = f(n-1) + f(n-2)【状态转移公式】

「 爬台阶问题 」 只是动态规划中相对简单的问题，因为它只有一个变化维度，如果涉及多个维度的话，那么问题就变得复杂多了。

难点就在于找出 「动态规划」中的这三个概念。

比如「 国王和金矿问题 」。

国王和金矿问题

有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

5 座金矿

找出 「动态规划」中的这三个概念

国王和金矿问题中的【最优子结构】

国王和金矿问题中的【最优子结构】

国王和金矿问题中的【最优子结构】有两个：

4 金矿的最优选择与 5 金矿的最优选择之间的关系是

MaX[（4 金矿 10 工人的挖金数量），（4 金矿 5 工人的挖金数量 + 第 5 座金矿的挖金数量）]

国王和金矿问题中的【边界】

国王和金矿问题中的【边界】 有两个：

国王和金矿问题中的【状态转移公式】

我们把金矿数量设为 n，工人数设为 W，金矿的黄金量设为数组G[]，金矿的用工量设为数组P[]，得到【状态转移公式】：

国王和金矿问题中的【实现】

先通过几幅动画来理解 「工人」 与 「金矿」 搭配的方式

1.只挖第一座金矿

只挖第一座金矿

在只挖第一座金矿前面两个工人挖矿收益为 零，当有三个工人时，才开始产生收益为 200，而后即使增加再多的工人收益不变，因为只有一座金矿可挖。

2.挖第一座与第二座金矿

挖第一座金矿与第二座金矿

在第一座与第二座金矿这种情况中，前面两个工人挖矿收益为 零，因为 W < 3,所以F(n,W) = F(n-1,W) = 0。

当有 三 个工人时，将其安排挖第 一 个金矿，开始产生收益为 200。

当有 四 个工人时，挖矿位置变化，将其安排挖第 二 个金矿，开始产生收益为 300。

当有 五、六 个工人时，由于多于 四 个工人的人数不足以去开挖第 一 座矿，因此收益还是为 300。

当有 七 个工人时，可以同时开采第 一 个和第 二 个金矿，开始产生收益为 500。

3.挖前三座金矿

这是「国王和金矿」 问题中最重要的一个动画之一，可以多看几遍

挖前三座金矿4.挖前四座金矿

这是「国王和金矿」 问题中最重要的一个动画之一，可以多看几遍

挖前四座金矿国王和金矿问题中的【规律】

仔细观察上面的几组动画可以发现：

国王和金矿问题中的【动态规划代码】

%ignoRe_pRe_7%

动态规划代码

希望通过这篇文章，大家能对「递归」与「动态规划」有一定的理解。