看动画轻松理解「递归」与「动态规划」

燕哥带你学算法

2019-06-30

关注关注

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

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

什么是递归

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

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

1. 一个问题的解可以分解为几个子问题的解
1. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
1. 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口

看动画轻松理解「递归」与「动态规划」

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

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

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

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

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

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

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

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

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

从递归的经典示例开始

一.数组求和

看动画轻松理解「递归」与「动态规划」

Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])

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

Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])

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

Sum(arr[n-1...n-1] ) = arr[n-1] + Sum([])

二.汉诺塔问题

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

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

看动画轻松理解「递归」与「动态规划」

① 如果只有 1 个盘子，则不需要利用 B 塔，直接将盘子从 A 移动到 C 。
② 如果有 2 个盘子，可以先将盘子 2 上的盘子 1 移动到 B ；将盘子 2 移动到 C ；将盘子 1 移动到 C 。这说明了：可以借助 B 将 2 个盘子从 A 移动到 C ，当然，也可以借助 C 将 2 个盘子从 A 移动到 B 。
③ 如果有 3 个盘子，那么根据 2 个盘子的结论，可以借助 C 将盘子 3 上的两个盘子从 A 移动到 B ；将盘子 3 从 A 移动到 C ，A 变成空座；借助 A 座，将 B 上的两个盘子移动到 C 。

④ 以此类推，上述的思路可以一直扩展到 n 个盘子的情况，将将较小的 n-1个盘子看做一个整体，也就是我们要求的子问题，以借助 B 塔为例，可以借助空塔 B 将盘子A上面的 n-1 个盘子从 A 移动到 B ；将A 最大的盘子移动到 C ， A 变成空塔；借助空塔 A ，将 B 塔上的 n-2 个盘子移动到 A，将 C 最大的盘子移动到 C， B 变成空塔。。。

三.爬台阶问题

问题描述：

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

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

看动画轻松理解「递归」与「动态规划」

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

看动画轻松理解「递归」与「动态规划」

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

① 第一类是第一步走了 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 个台阶，有两种走法，一步走完或者分两步来走。

总结如下：

① 假设只有一个台阶，那么只有一种走法，那就是爬 1 个台阶
② 假设有两个个台阶，那么有两种走法，一步走完或者分两步来走

看动画轻松理解「递归」与「动态规划」

通过递归条件：

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

很容易推导出递归代码：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

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

1.找到如何将大问题分解为小问题的规律
2.通过规律写出递推公式
3.通过递归公式的临界点推敲出终止条件
4.将递推公式和终止条件翻译成代码

什么是动态规划

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

分治策略

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

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

动态规划（Dynamic Programming）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

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

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

1.动态规划法试图只解决每个子问题一次
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

从递归到动态规划

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

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

看动画轻松理解「递归」与「动态规划」

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

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

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

台阶数	1	2	3	4	5	6	7	8	9
走法数	1	2

表格的第一行代表了楼梯台阶的数目，第二行代表了若干台阶对应的走法数。
其中f(1) = 1 和 f(2) = 2是前面明确的结果。

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

台阶数	1	2	3	4	5	6	7	8	9
走法数	1	2	3

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

台阶数	1	2	3	4	5	6	7	8	9
走法数	1	2	3	5

看动画轻松理解「递归」与「动态规划」

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

show me the code

int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // a 保存倒数第二个子状态数据，b 保存倒数第一个子状态数据， temp 保存当前状态的数据
    int a = 1, b = 2;
    int temp = a + b;
    for (int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

程序从 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 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

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

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

看动画轻松理解「递归」与「动态规划」

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

① 4 金矿 10 工人的最优选择
② 4 金矿（10 - 5）工人的最优选择

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

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

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

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

① 当只有 1 座金矿时，只能挖这座唯一的金矿，得到的黄金数量为该金矿的数量
② 当给定的工人数量不够挖 1 座金矿时，获取的黄金数量为 0

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

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

边界值：F(n,w) = 0 (n <= 1, w < p[0])
F(n,w) = g[0] (n==1, w >= p[0])
F(n,w) = F(n-1,w) (n > 1, w < p[n-1])
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1]) + g[n-1]) (n > 1, w >= p[n-1])

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

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

1.只挖第一座金矿

看动画轻松理解「递归」与「动态规划」

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

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

看动画轻松理解「递归」与「动态规划」

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

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

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

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

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

3.挖前三座金矿

这是「国王和金矿」问题中最重要的一个动画之一，可以多看几遍
看动画轻松理解「递归」与「动态规划」

4.挖前四座金矿

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

看动画轻松理解「递归」与「动态规划」

国王和金矿问题中的【规律】

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

对比「挖第一座与第二座金矿」和「挖前三座金矿」，在「挖前三座金矿」中，3 金矿 7 工人的挖矿收益，来自于 2 金矿 7 工人和 2 金矿 4 工人的结果，Max(500,300 + 350) = 650；
对比「挖前三座金矿」和「挖前四座金矿」，在「挖前四座金矿」中，4 金矿 10 工人的挖矿收益，来自于 3 金矿 10 工人和 3 金矿 5 工人的结果，Max(850,400 + 300) = 850；

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

代码来源：https://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html

//maxGold[i][j] 保存了i个人挖前j个金矿能够得到的最大金子数，等于 -1 时表示未知
int maxGold[max_people][max_n];

int GetMaxGold(int people, int mineNum){
    int retMaxGold;                            //声明返回的最大金矿数量
    //如果这个问题曾经计算过
    if(maxGold[people][mineNum] != -1){
        retMaxGold = maxGold[people][mineNum]; //获得保存起来的值
    }else if(mineNum == 0) {                   //如果仅有一个金矿时 [ 对应动态规划中的"边界"]
        if(people >= peopleNeed[mineNum])      //当给出的人数足够开采这座金矿
            retMaxGold = gold[mineNum];        //得到的最大值就是这座金矿的金子数
        else                                   //否则这唯一的一座金矿也不能开采
            retMaxGold = 0;                    //得到的最大值为 0 个金子
    }else if(people >= peopleNeed[mineNum])    // 如果人够开采这座金矿[对应动态规划中的"最优子结构"]
    {
        //考虑开采与不开采两种情况，取最大值
        retMaxGold = max(
                         GetMaxGold(people - peopleNeed[mineNum],mineNum - 1) + gold[mineNum],
                         GetMaxGold(people,mineNum - 1)
                         );
    }else//否则给出的人不够开采这座金矿 [ 对应动态规划中的"最优子结构"]
    {
        retMaxGold = GetMaxGold(people,mineNum - 1);     //仅考虑不开采的情况
        maxGold[people][mineNum] = retMaxGold;
    }
    return retMaxGold;
}

看动画轻松理解「递归」与「动态规划」

希望通过这篇文章，大家能对「递归」与「动态规划」有一定的理解。后续将以「动态规划」为基础研究多重背包算法、迪杰特斯拉算法等更高深的算法问题，同时「递归」的更多概念也会在「分治算法」章节再次延伸，敬请对程序员小吴保持关注：）

递归动态规划递归算法递归调用 sum

看动画轻松理解「递归」与「动态规划」

什么是递归

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

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

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

从递归的经典示例开始

一.数组求和

二.汉诺塔问题

三.爬台阶问题

什么是动态规划

分治策略

动态规划（Dynamic Programming）

从递归到动态规划

详解动态规划

国王和金矿问题

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

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

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

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

1.只挖第一座金矿

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

3.挖前三座金矿

4.挖前四座金矿

国王和金矿问题中的【规律】

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

相关推荐