如何理解动态规划

ゝ一世哀愁。 2023-10-01 19:29 13阅读 0赞

### 1. 动态规划 ###

动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把**原问题分解为相对简单的子问题**的方式求解复杂问题的方法。

**动态规划问题的一般形式就是求最值**。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求**最长**递增子序列，**最小**编辑距离等等。

动态规划常常适用于有**重叠子问题**和**最优子结构**性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有**自底向上**和**自顶向下**两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做**无后效性**，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然**剪枝**的功能，从而减少计算量。

这是[leetcode][]上面的概念，我们可以把他结构化一下，并理解一下具体的概念。

![image-20210913104321193][]

**1、什么是最优子结构？**

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

可以反向理解，我们可以通过子问题的最优解，推导出问题的最优解，也就是子找父。如果我们把最优子结构，对应到我们前面定义的动态规划上，那我们也可以理解为，**原问题可以通过子问题推导出来**，如`F(10) = F(9)+F(8)`，则`F(9)`和`F(8)`是`F(10)`的最优子结构。

**2、什么是重叠子问题？**

递归算法求解问题时，每次产生的子问题并不总是新问题，有些**子问题被反复计算多次**，这种性质称为子问题的重叠性质。

[**3、什么是无后效性？**][3]

某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。

### 2. 斐波拉契数列 ###

斐波那契数列指的是这样一个数列：

![image-20210913112547375][]

这个数列数列从第 3 项开始，每一项都等于前两项之和。其递推公式为：

F(0) = 0，F(1) = 1
    F(n) = F(n - 1) + F(n - 2)，其中 n > 1

#### 2.1 暴力递归 ####

我们通过递归的方式来实现一个斐波那契数列

public int fib(int n) {
        
        if (n == 0) {
        
            return 0;
        }
        if (n == 1) {
        
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

可以看到在[leetcode][leetcode 1]运行上并不是很优秀。

![image-20210913113734097][]

我们来分析一下它的执行过程，假如我们要求`n=6`的值，则其递归树如下：

![image-20210913144609538][]

可以看到，上面每个节点都会执行一次，而且存在重复执行的节点，这也就是**重叠子问题**性质的表现，如`fib(2)`被重复执行了 5 次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。

我们试着用动态规划的**自底向上**和**自顶向下**方式来解决斐波拉契数列问题。

#### 2.2 自顶向下备忘录 ####

在递归方法中如果要计算原问题 `f(20)`的值，就得先计算出子问题 `f(19)` 和 `f(18)`，然后要计算 `f(19)`，我就要先算出子问题 `f(18)` 和 `f(17)`，以此类推。最后遇到 `f(1)` 或者 `f(2)` 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

![image-20210913145627020][]

因此，我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然也可以使用哈希表。

private Map<Integer, Integer> memo = new HashMap<>();
    //备忘录法
    public int fib(int n) {
        
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (memo.containsKey(n)) {
        
            return memo.get(n);
        } else {
        
            int value = fib(n - 1) + fib(n - 2);
            memo.put(n, value);
            return value;
        }
    }

再次查看时间消耗，很明显耗时减少。

![image-20210913143212839][]

**「备忘录」到底做了什么？**

当计算 `f(20)`的值，先计算出 `f(19)` 和 `f(18)`，而在计算`f(19)`的值时，已经把`f(18)`的值计算出来了。

![image-20210913150539383][]

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数，即：

![image-20210913151214786][]

#### 2.3 自底向上动态规划 ####

可以看到，备忘录法还是利用了递归，计算`fib(20)`的时候还是要计算出`fib(19)`，`fib(18)`，`fib(17)`…，如果我们先计算出`fib(1)`，`fib(2)`，`fib(3)`…呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

因为我们已经知道`fib(0)`和`fib(1)`的值，实际上，`fib(2)`的值也是知道的，即：

fib(2) = fib(0) + fib(1) = 1
    fib(3) = fib(1) + fib(2) = 2
    fib(4) = fib(2) + fib(3) = 3
    fib(5) = fib(3) + fib(4) = 5
    fib(6) = fib(4) + fib(5) = 8
    ......

我们根据备忘录的思想，用一张表来记录，即：

![image-20210913161559976][]

public int fib(int n) {
        
        if (n == 0) return 0;
        //dp表，n+1是因为0~n,有n+1个数
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
        
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

看看实际效果：

![image-20210913161644191][]

另外，我们可以看到尽管用数组自底向上保存了先计算的值，但实际上参与循环计算的始终只有`i,i-1,i-2`这3项，即

![image-20210913165629994][]

因此，可以把上面的代码优化为：

public int fib(int n) {
        
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 1;
        int b = 1;
        int temp = 0;//temp即为下一次循环的b的值
        for (int i = 3; i <= n; i++) {
        
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }

### 3. 动态规划基本设计步骤 ###

当然，斐波拉契数列只是一个超级简单的动态规划的引子，也就是说刚入门，但是我们确可以从中得到一些启发，对于动态规划，无非就是利用**历史记录**，来避免我们的重复计算。而这些**历史记录**，我们得需要一些**变量**来保存，一般是用**一维数组**或者**二维数组**来保存。因此，我们可以总结出**动态规划基本设计步骤**：

1.  **数组元素的含义**，即`dp[]`，如自底向上的解法，`dp[n]`就代表第`n`项的值。
2.  **数组元素之间的关系式（或者叫状态转移方程）**，当我们要计算 `dp[n]` 时，是可以利用 `dp[n-1],dp[n-2]… dp[1]`，来推出 `dp[n]` ，也就是可以利用**历史数据**来推出新的元素值，所以我们要找出数组元素之间的关系式，如 `dp[n] = dp[n-1] + dp[n-2]`，当然这个不同题意，关系式也不同，同时也是难点。
3.  **初始值**，也就是 dp 中的边界情况，我们通过公式`dp[n] = dp[n-1] + dp[n-2]`去递推，当递推到 `dp[2] = dp[1] + dp[0]`，此时`dp[1]` 和 `dp[0]` 不能再分解，因此我们必须要知道`dp[1]` 和 `dp[0]` 的值。

下面通过几个例子来实战一下。

#### [3.1 爬楼梯][3.1] ####

> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
> 
> 每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？（n 为正整数）

我们按照上面的步骤来分析。

**1、定义数组元素的含义**

假设跳上一个 n 阶的台阶总共有`dp(n)`种跳法。

**2、定义数组元素之间的关系式**

把原问题拆分为子问题，因为每次可以爬 1 或 2 个台阶，因此：

第一层：1种,记为dp(1)=1,n=1
    
    第二层：2种（走2步或走两个1步）,记为dp(2)=2,n=2
    
    第三层：3种（走3个1步或在第一层走2步或在第二层走1步）,记为dp(3)=dp(1)+dp(2),n=3
    
    ......

因此第 n 层与第 n-1 和第 n-2 层有关。即到达第 n 级的台阶有两种方式：

*  一种是从第 n-1 级跳上来
 *  一种是从第 n-2 级跳上来

即：`dp[n] = dp[n-1] + dp[n-2]`

很明显可以看出，其实就是一个斐波拉契数列，唯一的区别就是**临界值**不同，这里的 n 不能为 0。

**3、初始值**

在第二步就已经得到其初始值为`dp(1)=1,dp(2)=2`，需要注意的就是**临界值**。

**代码实现**

public int climbStairs(int n) {
        
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
        
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

#### [3.2 不同路径][3.2] ####

> 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

![image-20210913193037546][]

还是按照上面的步骤来分析：

**1、定义数组元素的含义**

题目是求从左上角到右下角有多少种路径，如果用函数来表示则是：`dp(i,j)`，假设`i,j`的位置就是目标点，则其取值范围分别为`[0,i)`和`[0,j)`。也就是说**当机器人从左上角走到`(i,j)` 这个位置时，一共有 `dp[i][j]` 种走法**。（很自然的一个二维数组，假设`i`表示向右走，`j`表示向下走）

**2、定义数组元素之间的关系式**

因为机器人每次只能向下或者向右移动一步，假设目标点是`(i,j)`，则分两种情况：

*  向下走一步到达，那么上一步的位置则是`(i-1,j)`；
 *  向右走一步到达，那么上一步的位置则是`(i,j-1)`。

因此，总共的走法则有：`dp[i][j] = dp[i-1][j] + dp[i][j-1]`

**3、初始值**

对于初始值，其实我们很好判定，如 `i = 0`或者`j = 0`（注：这里的`0`表示的数组下标），那么此时对于上面的表达式是不存在的，即为负数了，所以我们可以设置边界条件，如下：

*  `i = 0`，表示横向只有一个格子，则只能一直往下走，很显然只有一条路径，`dp[0][j] = 1`；
 *  `j = 0`，表示纵向只有一个格子，则只能一直往右走，很显然也只有一条路径，`dp[i][0] = 1`；

**代码实现**

public int uniquePaths(int m, int n) {
        
       
        int[][] dp = new int[m][n];
        // 赋初始值
        for (int i = 0; i < m; i++) {
        
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
        
            dp[0][j] = 1;
        }
        // 从 1 开始
        for (int i = 1; i < m; i++) {
        
            for (int j = 1; j < n; j++) {
        
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 注意数组从 0 开始，所以要 -1
        return dp[m-1][n-1];
    }

*  时间复杂度：O(m\*n)
 *  空间复杂度：O(m\*n)

#### 3.3 [最长公共子序列][Link 1] ####

> 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
> 
> 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
> 
> **例如**，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
> 
> 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
> 
> **示例 1：**
> 
> 输入：text1 = “abcde”, text2 = “ace”  
> 输出：3  
> 解释：最长公共子序列是 “ace” ，它的长度为 3 。

**注：子序列可以是不连续的，子字符串需要是连续的。**

先分析一下，假如现在有字符串如下：

text1 = abfeghac
    
    text2 = cabfeghc

**1、定义数组元素的含义**

还是老样子，2 个字符串，对应 2 个二维数组，思路如下：

1.  把两个字符串分别以**行和列**组成一个二维的矩阵；
2.  比较二维矩阵中每个点对应**行列**字符中否相等，相等的话值设置为 1，否则设置为 0；
3.  通过查找出值为1的最长对角线就能找到最长公共子串。

![image-20220128192227767][]

从上图可以看出，有 4 个公共子串，且最长公共子串为 7，`abfeghc`（为什么是 7 ，注意上面对子序列的描述）。

但这存在一个问题，我们还得再去计算这个公共子串的长度，因此我们在计算这个二维矩阵的时候顺带着计算出这个子串的长度，用`i`、`j`表示两个子串的长度， `dp[i][j]`表示其公共长度，如下：

![image-20220128194540399][]

`dp[i][j]` ，其含义是在 `text1[0,i-1]` 与 `text2[0,j-1]` 之间匹配得到的想要的结果。

注：`i`、`j`表示两个数组的长度，所以定义的数组范围是`0 ~ i-1`，因此`i-1`表示最后一位字符，`j`同理。

**2、定义数组元素之间的关系式**

从上图中我们可以看出，存在两种情况，即 2 个字符串存在相等的字符：

*  当`text1[i-1] == text2[j-1]`时，说明两个字符串**最后一位**有相等的字符，所以公共子序列`+1`，即`dp[i][j] = dp[i-1][j-1]+1`。
 *  当`text1[i-1] != text2[j-1]`时，说明两个字符串**最后一位**没有相等的字符，最后一个元素不相等，那说明最后一个元素不可能是最长**公共**子序列中的元素，此时存在 2 种情况，`dp[i-1][j]`和`dp[i][j-1]`，其中：
    
     *  `dp[i-1][j]`：表示最长公共序列可以在`1,2,3,...,i-1`和 `1,2,3,...,j`中找。
     *  `dp[i][j-1]`：表示最长公共序列可以在`1,2,3,...,i`和 `1,2,3,...,j-1`中找。
    
    求解上面两个子问题，得到的公共子序列谁最长，谁就是最长子序列，即`dp[i][j] = max(dp[i−1][j],dp[i][j−1])`。

综上，状态转移方程为：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j − 1 \] + 1 , t e x t 1 \[ i − 1 \] = t e x t 2 \[ j − 1 \] m a x ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − 1 \] ) , t e x t 1 \[ i − 1 \] ≠ t e x t 2 \[ j − 1 \] dp\[i\]\[j\] = \\begin\{cases\} dp\[i-1\]\[j-1\]+1, & text\_1\[i-1\] = text\_2\[j-1\] \\\\ \\\\ max(dp\[i-1\]\[j\],dp\[i\]\[j-1\]), & text\_1\[i-1\] \\neq text\_2\[j-1\] \\end\{cases\} dp\[i\]\[j\]=⎩⎪⎨⎪⎧dp\[i−1\]\[j−1\]\+1,max(dp\[i−1\]\[j\],dp\[i\]\[j−1\]),text1\[i−1\]=text2\[j−1\]text1\[i−1\]=text2\[j−1\]  
**3、初始值**

当`i=0`或者`j=0`时，即是空串和字符串来比较，结果肯定为 0 ，即`dp[0][j]=0` ，`dp[i][0]=0`。

由于 `dp[i][j]` 依赖与 `dp[i-1][j-1] , dp[i-1][j], dp[i][j-1]`，所以 `i` 和 `j`的遍历顺序肯定是从小到大的。

另外，由于当 `i`和 `j` 取值为 0 的时候，`dp[i][j] = 0`，而 dp 数组本身初始化就是为 0，所以，直接让 `i` 和 `j`从 1 开始遍历。遍历的结束应该是字符串的长度。

**代码实现**

public int longestCommonSubsequence(String text1, String text2) {
        
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
        
            for (int j = 1; j <= n; j++) {
        
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
        
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
        
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

### 4. 总结 ###

实际上动态规划的问题主要就是掌握其性质，**最优子结构和重叠子问题**，即把大的问题拆分为一个个小的问题，在按照上面的几个步骤来解决问题。

当然，练习是必不可少的，熟能生巧。

### 5. 参考 ###

*  https://hollis.blog.csdn.net/article/details/103045322
 *  https://blog.csdn.net/u010397369/article/details/38979077

[leetcode]: https://leetcode-cn.com/tag/dynamic-programming/problemset/
[image-20210913104321193]: https://img-blog.csdnimg.cn/img_convert/95cc988f1031c159bbd7a0d5d8a36b12.png
[3]: https://blog.csdn.net/qq_30137611/article/details/77655707
[image-20210913112547375]: https://img-blog.csdnimg.cn/img_convert/78821985ea44dc65e775b7f0d6231a54.png
[leetcode 1]: https://leetcode-cn.com/problems/fibonacci-number/
[image-20210913113734097]: https://img-blog.csdnimg.cn/img_convert/1bb033a17e8f1a3dab559210097af110.png
[image-20210913144609538]: https://img-blog.csdnimg.cn/img_convert/00a04b7c811bfeb80ff0c68b2aaf1b51.png
[image-20210913145627020]: https://img-blog.csdnimg.cn/img_convert/4eeac3b46f799291776378db02dff21a.png
[image-20210913143212839]: https://img-blog.csdnimg.cn/img_convert/d8c913a951f623d0ad2b8de0c6a78e83.png
[image-20210913150539383]: https://img-blog.csdnimg.cn/img_convert/eecd607de398f023f12800161c2ae849.png
[image-20210913151214786]: https://img-blog.csdnimg.cn/img_convert/ebf3ab16573b05247c83a7b33d8c5297.png
[image-20210913161559976]: https://img-blog.csdnimg.cn/img_convert/cab0f3be1827159730da1c2014ee5592.png
[image-20210913161644191]: https://img-blog.csdnimg.cn/img_convert/269d902f1e463892939d7ebed6ceca02.png
[image-20210913165629994]: https://img-blog.csdnimg.cn/img_convert/1a4175c1a2290dc26255ed6886485ef6.png
[3.1]: https://leetcode-cn.com/problems/climbing-stairs/
[3.2]: https://leetcode-cn.com/problems/unique-paths/
[image-20210913193037546]: https://img-blog.csdnimg.cn/img_convert/dc4c863929385c9e2fd194fa5c42b5a4.png
[Link 1]: https://leetcode-cn.com/problems/longest-common-subsequence/
[image-20220128192227767]: https://img-blog.csdnimg.cn/img_convert/52886a37b094c924795c505d8257def5.png
[image-20220128194540399]: https://img-blog.csdnimg.cn/img_convert/9b6233267e2f8ff0d46cb4a0fa48293f.png