学妹半夜问我动态规划是咋回事，我啪的一下讲清楚了！

墨蓝 2023-01-21 09:20 4阅读 0赞

事情是这样的，临近期末考试，学妹突然问我动态规划怎么理解，本着友好互助的原则，不顾女朋友的反对，花了五分钟给她讲清楚，先不说其它的了，你们先看文章，我去跪一会榴莲。

### 什么是递归 ###

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

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

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

![递归动画][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9jaTY3eC5naWY]

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

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

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

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

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

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

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

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

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

### 从递归的经典示例开始 ###

#### 一.数组求和 ####

![数组求和][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9memFuNS5naWY]

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个座上的盘子始终保持大盘在下，小盘在上。

![两个盘子][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9paW02Yy5naWY]

![三个盘子][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9wMGJrYy5naWY]

*  ① 如果只有 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 个台阶爬完楼梯：

![每次爬 1 个台阶][1]

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

![先爬 2 个台阶][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 个台阶，有两种走法，一步走完或者分两步来走。

总结如下：

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

![递归终止条件][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy80YTZvNy5naWY]

通过递归条件：

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)，具体的计算可以查看笔者之前的文章 《冰与火之歌：时间复杂度与空间复杂度》。

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

![爬台阶的时间复杂度][format_png]

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

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

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

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

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

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

![aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9rN2d2Zi5naWY][]

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

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

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

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

![国王和金矿问题中的【最优子结构】][format_png 1]

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

*  ① 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.只挖第一座金矿 ######

![只挖第一座金矿][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9hd3ZxMS5naWY]

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

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

![挖第一座与第二座金矿][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9kMHRidi5naWY]

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

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

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

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

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

###### 3.挖前三座金矿 ######

**这是「国王和金矿」 问题中最重要的一个动画之一，可以多看几遍**  
![挖前三座金矿][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy8zdWMyOS5naWY]

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

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

![挖前四座金矿][aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9qcGVsYy5naWY]  
[《LeetCode刷题C/C++版答案》pdf出炉，白瞟党乐坏了][LeetCode_C_C_pdf]

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

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

*  对比「挖第一座与第二座金矿」和「挖前三座金矿」，在「挖前三座金矿」中，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;
    }

![动态规划代码][format_png 2]

[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9jaTY3eC5naWY]: /images/20221020/80fa60c2cb7b4d41a10b28ccd24968b2.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9memFuNS5naWY]: /images/20221020/00458aa2df324bb69647e4f926c90b2f.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9paW02Yy5naWY]: /images/20221020/e09d6fa22f3a45449896c971968e8e3f.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9wMGJrYy5naWY]: /images/20221020/afd0bce5215c4037b31722c234bc07cb.png
[1]: /images/20221020/0c9edbcc2c1b43b2be23600131a3d0eb.png
[2]: /images/20221020/f78a1c6530b54a4d80d0c77e5c95a86c.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy80YTZvNy5naWY]: /images/20221020/9a683cf5ddce474d8be9069108f042cf.png
[format_png]: /images/20221020/0e4649aa457e48a398b28fff67a217c9.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9rN2d2Zi5naWY]: /images/20221020/8fcc9fff962242869c2dc82ac8eb617d.png
[5]: /images/20221020/20ffb49243054cc0a820c90bb597e960.png
[format_png 1]: /images/20221020/f0944855a9f643449b068e87b2969099.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9hd3ZxMS5naWY]: /images/20221020/d3d76c76600a4dc59e53534a2db75026.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9kMHRidi5naWY]: /images/20221020/a911aa6e29f44dbf8447aba9828060ef.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy8zdWMyOS5naWY]: /images/20221020/706965920fea4430a5fca17687d04fb8.png
[aHR0cHM6Ly9ibG9nLTEyNTcxMjY1NDkuY29zLmFwLWd1YW5nemhvdS5teXFjbG91ZC5jb20vYmxvZy9qcGVsYy5naWY]: /images/20221020/cdd8c6fca88b4845b9f62632d2cd7737.png
[LeetCode_C_C_pdf]: https://blog.csdn.net/kexuanxiu1163/article/details/115792685
[format_png 2]: /images/20221020/08f3e612026049ca8685223a482e6527.png