动态规划总结

2020-11-12 本文已影响0人郑小才

动态规划的三大步骤

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤。

1. 定义数组元素的含义
  我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
1. 找出数组元素之间的转移方程
  动态规划，有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。
1. 找出初始值
  学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

案例一

最小路径和(leetcode 的第64题)

问题描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。举例：
输入:
arr = [
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
1. 定义数组元素的含义
  由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，最下的路径和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我们要的答案了。

注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以由下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要走的答案。

1. 找出关系数组元素间的转移方程
  想象一下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达一种是从 (i-1, j) 这个位置走一步到达，另一种是从(i, j - 1) 这个位置走一步到达不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的，那么我们要从这两种方式中，选择一种，使得dp[i] [j] 的值是最小的，显然有

dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值

1. 找出初始值。
  当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。
  因此初始值如下：

dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行，机器人只能一直往左走
dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列，机器人只能一直往下走

代码如下

public static int uniquePaths(int[][] arr) {
    int m = arr.length;
    int n = arr[0].length;
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n]; // 
    // 初始化
    dp[0][0] = arr[0][0];
    // 初始化最左边的列
    for(int i = 1; i < m; i++){
      dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 初始化最上边的行
    for(int i = 1; i < n; i++){
      dp[0][i] = dp[0][i-1] + arr[0][i];
    }
        // 推导出 dp[m-1][n-1]
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[m-1][n-1];
}

案例二

编辑距离(leetcode 的第题72)

问题描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例：

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解答
还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。
定义数组元素的含义
由于我们的目的求将 word1 转换成 word2 所使用的最少操作数。那我们就定义 dp[i] [j]的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。

有时候，数组的含义并不容易找

找出关系数组元素间的转移方程
接下来我们就要找 dp[i] [j] 元素之间的关系了，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，从规模小的，通过一些操作，推导出规模大的。
对于这道题，我们可以对 word1 进行三种操作：插入一个字符删除一个字符替换一个字符。由于我们是要让操作的次数最小，所以我们要寻找最佳操作。
那么有如下关系式：
- 1. 如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。
- 1. 如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
  - 1. 如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1。
  - 1. 如果在字符串 word[i]末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1。
  - 1. 如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1。

我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有

dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1

找出初始值
显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。

代码如下

public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // dp[0][0...n2]的初始值
    for (int j = 1; j <= n2; j++) 
        dp[0][j] = dp[0][j - 1] + 1;
    // dp[0...n1][0] 的初始值
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
        // 通过公式推出 dp[n1][n2]
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                p[i][j] = dp[i - 1][j - 1];
            }else {
               dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }         
        }
    }
    return dp[n1][n2];  
}

优化

画图！画图！画图

80% 的动态规划题都可以画图，其中 80% 的题都可以通过画图一下子知道怎么优化，当然，DP 也有一些很难的题，想优化可没那么容易，不过，今天我要讲的，是属于不怎么难，且最常见，面试笔试最经常考的难度的题。下面我们直接通过三道题目来讲解优化，你会发现，这些题，优化过后，代码只有细微的改变，你只要会一两道，可以说是会了 80% 的题。

案例一（最短路径数）优化
前面的做法的空间复杂度是 O(n * m)，下面我们来讲解如何优化成 O(n)。
dp[i] [j] 是一个二维矩阵，我们来画个二维矩阵的图，对矩阵进行初始化。
然后根据公式 dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j] 来填充矩阵的其他值。
根据公式我们知道当我们要填充某一行的值的时候，我们只需要用到上一行的值，而不需要用到更前面的行的值，也就是说，我们只需要用一个一维的 dp[] 来保存一行的历史记录就可以了，然后在计算机的过程中，不断着更新 dp[] 的值。

画图演示下这个过程

原始数据

1	3	1
1	5	1
4	2	1

根据原始数据，算出第一行。

1	4	5

根据原始数据和第一行算出第二行

2	7	6

根据原始数据和第二行算出第三行

6	8	7

最后得到结果 7

转移方程
由
dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]
变为
dp[j] = Math.min(dp[j], dp[j - 1]) + arr[i][j]

优先代码后代码

      public static int uniquePaths(int[][] arr) {
        int n = arr[0].length;
        int[] dp = new int[n]; //
        // 初始化最上边的行
        dp[0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + arr[0][i];
        }
        // 推导出 dp[n-1]
        for (int i = 1; i < arr.length; i++) {
            dp[0] = dp[0] + arr[i][0];//j为0的时候直接在累加当前单元格的值
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + arr[i][j];
            }
        }
        return dp[n - 1];
    }

Leetcode 动态规划直达：https://leetcode-cn.com/tag/dynamic-programming/
参考：https://www.zhihu.com/question/291280715/answer/1570410869

动态规划总结

动态规划的三大步骤

案例一

案例二

优化

猜你喜欢

热点阅读