文章目录

前言：最近在力扣刷题，但是之前从没有接触过算法题，有的看答案都看不懂，后来做的题做多了发现有好多类似的题目，所以我打算总结一下规律。

  • 人无完人，设想地球上的每个超棒的想法都能汇聚在相应的小河之中，那么文明的大河将会迅速变成大海（赶在太阳将河水蒸干之前）。感谢互联网，让开源共享精神照耀了这个时代，让这个设想有了真正的可能。

  • 如果你想了解更多可以去看文末的参考文章，我觉得他们讲的都特别好，此篇博客也参考了很多他们的内容。

一、动态规划的思想

分享一个故事：

来源：见底部参考文章

A * "1+1+1+1+1+1+1+1 =？" *

A : "上面等式的值是多少"
B : *计算* "8!"

A : *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

动态规划算法的核心就是记住已经解决过的子问题的解。

动态规划的思想和表达方式都非常简单，求一个问题的解，先得准确的找到该问题所包含的重叠子问题。

– 什么是重叠子问题？

所谓重叠子问题，就是在求解原问题的解的过程中需要大量重复求解的子问题

求出其重叠子问题的解并将其记录以备再次使用，这样可以大量削减搜索的开销，提高时间复杂度。

  • 态规划是在尝试了一个问题的每一种可能的解之后，再从中找出最优解。
  • 动态规划是一种既保证正确性又非常高效的算法。

动态规划经典类型：(最后面会详细讲解背包问题)

  • 背包
  • 树型
  • 计数动态规划

求解的方式: （后面有例题）

  • a. 自顶向下的备忘录法
  • b. 自顶向上

说了那么多理论,相信大家还是蒙的,好的,下面举栗子。

二、动态规划的简单应用

下面是一个斐波那契数列的简单实现：

public int fib(int n)
{
    if(n<=0) {
    	return 0;
    }
        
    if(n==1) {
    	return 1;
    }
    
    return fib( n-1)+fib(n-2);
}
//输入6
//输出：8

这段代码很简单吧，其实程序就是这样的，执行效率和编写效率永远是成反比的，更让人头疼的是公司只要执行效率（我管你编写有多难呢），这也是我们学习数据结构的原因（应付面试与考研 ）。

算法的执行流程是这样的：

但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

问：递归算法的时间复杂度怎么计算？
答：子问题个数乘以解决一个子问题需要的时间。

  • 子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
  • 解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
  • 所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。

好了，有了栗子，我们看一下该怎么分析，怎么用动态规划处理它：

我们先用第一种方法解决:

a. 自顶向下的备忘录法

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(4) 被计算了两次，而且你可以看到，以 f(4) 为根的这个递归树体量又大，多算一遍，会耗费巨大的时间。更何况，还不止 f(4) 这一个节点被重复计算，所以这个算法及其低效。

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

那么问题是怎么判断有没有存过呢？

  • 先给数组赋初值
  • 如果循环的时候发现不等于这个初值了，就说明已经存过了
  • 然后返回这个值，就免去了一次遍历

这就是备忘录法的大致思想。下面我们用java代码实现以下：

public int fib1(int n) {
        //新建一个数组用于存储计算过的值
        int[] Memo = new int[n + 1];

        //初始值的判断
        if (n <= 0) {
            return n;
        }

        //给数组赋初值
        for (int i = 0; i <= n; i++) {
            Memo[i] = -1;
        }

        return fib2(n, Memo);
    }

    public int fib2(int n, int Memo[]) {

        //如果不等于初值-1了,说明已经计算过了
        if (Memo[n] != -1) {
            return Memo[n];
        }

        if (n <= 2) {
            Memo[n] = 1;
        } else {
            Memo[n] = fib2(n-1, Memo) + fib2(n-2, Memo);
        }

        return Memo[n];
    }

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

我们还有一个问题：
Q：递归算法的时间复杂度怎么算？
A：子问题个数乘以解决一个子问题需要的时间。

  • 子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) ... f(6)，数量和输入规模 n = 6成正比，所以子问题个数为 O(n)。
  • 解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。
  • 所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

至此，带备忘录的递归解法的效率已经和动态规划一样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

那么问题来了：

啥叫「自顶向下」？

注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(6)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(6)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

b. 自底向上的动态规划

上面的解法还是用到了递归，计算最大的元素的时候还是要回过头去计算最小的，只是只计算一次了，那为什么不能直接从最小的开始算呢？下面我们就来实现一下自底向上的方法：

这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

public int fib3(int n) {
        if (n<=0) {
            return n;
        }
        int[] Memo = new int[n+1];
        Memo[0] = 1;
        Memo[1] = 1;

        for (int i = 2; i <= n; i++) {
            Memo[n] = Memo[n-1] + Memo[n-2];
        }
        return Memo[n];
    }

自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。观察参与循环的只有 i，i-1 , i-2三项，因此该方法的空间可以进一步的压缩如下。

public int fib4(int n) {
        if (n<=1) {
            return n;
        }

        int Memo_i = 1;
        int Memo_i_1 = 1;
        int Memo_i_2 = 0;

        for (int i = 2; i <= n; i++) {
            Memo_i = Memo_i_2 + Memo_i_1;
            Memo_i_2 = Memo_i_1;
            Memo_i_1 = Memo_i;
        }
        
        return Memo_i;
    }
  • 一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。
  • 你以为看懂了上面的例子就懂得了动态规划吗？那就too young too simple了。动态规划远远不止如此简单。

这里再介绍一种自己总结的解决问题很好的方法：

动态规划的三大步骤

1、定义数组元素的含义

就是你要求什么。

  • 我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

这里斐波那契数列元素仅仅代表数字，很容易理解，但有的题目就很难理清楚。

2、找出数组元素之间的关系式

就是往后退一步，看他是怎么求出来的。

  • 我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步。

这里斐波那契数列的关系式就是dp[n] = dp[n-1] + dp[n-2];

3、找出初始值

就是看看那个是不能通过公式求出来的。

  • 学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 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[0]=0和dp[1]=1是初始值,所有的数据都是基于他们两个得出来的，如果你仔细看那张图你会发现，最底层永远是这两个初始值。

好了，目前为止我们的引言案例已经介绍完了，带你体验一下动态规划，让你对它感兴趣，下面步入正题：

案例详解

1. 案例一：简单的一维 DP

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

声明一下：我们这里不做那种特别难的题目，因为没什么意义，我们只是入门而已，如果你对这个算法感兴趣，可以去Leelcode找一些题目做做。

好了,看这道题目，耗时根据我们的3步骤来解决这道题目，这道题相较于斐波那契数列抽象了一点，需要我们自己从题目中分析条件：

1.定义数组元素的含义：你要求什么

按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样，如果我们能够算出 dp[n]，不就是我们要求的答案吗？

求什么设什么，好熟悉啊，这也是我们做数学应用题的时候用的方法。

所以第一步定义完成。

2.找出数组元素之间的关系式：往后退一步

我们的目的是要求 dp[n]，动态规划的题就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3.... 也就是说，dp[n] 一定会和 dp[n-1], dp[n-2]…存在某种关系的。我们要找出他们的关系。

那么问题来了，怎么找？

这个是动态规划问题中最为核心也是最难的部分。我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？

对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式

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

但是我们是要算所有可能的跳法的，所以有 <mark>dp[n] = dp[n-1] + dp[n-2]</mark>。

分而治之！！！体会到了没有，因为dp[n-1]也有两种情况:

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

是不是又绕回去了?
对,这就是思想的核心。

3.找出初始值：找出公式求不出的值

当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0.（因为 0 个台阶，那肯定是 0 种跳法了）。于是得出初始值：

dp[0] = 0. dp[1] = 1.

即 n <= 1 时，dp[n] = n.

这样对吗？

我们不妨试一下，将2代进去，当有两个台阶的时候有几种跳法？

两种！ 一种是一次跳一个跳两次，一种是跳两个一步到位。

这么说dp[2]=2;

但是公式得出的是：dp[2] = dp[0] + dp[1] = 0 + 1 = 1;

所以在寻找初始值的时候，一定要注意不要找漏了，dp[2] 也算是一个初始值，不能通过公式计算得出。

  • Q: 有什么办法能避免这种错误吗?
  • A: 有，很简单，多做几道题你就会了。
  • Q: 。。。。

代码实现：

int f( int n ){
    if(n <= 2)
    return n;
    // 先创建一个数组来保存历史数据
    int[] dp = new int[n+1];
    // 给出初始值
    dp[0] = 0;
    dp[1] = 1;
    // 通过关系式来计算出 dp[n]
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 把最终结果返回
    return dp[n];
}

2. 案例二：二维数组的 DP

80% 的题，都是要用二维数组的，所以下面的题主要以二维数组为主。

  • Q：要用一维还是二维，我怎么知道？
  • A：这个问题不大，接着往下看。

问题描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

1. 定义数组元素的含义：你要求什么

这个应该不难想出来含义应该是dp[i][j] = 从起点出发到达第i,j位置的路径条数

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

2. 找出数组元素间的关系式：往后退一步

想象以下，机器人要怎么样才能到达 (i, j) 这个位置？
从终点往后退一步再看。
由于机器人只能向下走或者向右走，所以有两种方式到达

  • 一种是从 (i-1, j) 这个位置走一步到达
  • 一种是从 (i, j-1) 这个位置走一步到达

因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

加起来这个字眼很重要，只要有总的，全部，和、这些字眼的题目，我们要立刻想到加起来。

3. 找出初始值：公式求不出的值

其实你只要把关系式写出来了，初始值就自然而然的出来了，你只需要看哪个数字是公式求不出来的，或者说那个数字是不能代进去的。

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了。所以我们就是要求这个不能用公式求出来的值来作为初始值。

所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算图中的第一行和第一列。

因此初始值如下：

  • dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往右走
  • dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走

好了，现在三个步骤都走完了，是不是很简单 呢？

代码实现：

public static int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n];
    
    // 初始化
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
    // 推导出 dp[m-1][n-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];
        }
    }
    return dp[m-1][n-1];
}

空间复杂度: O(n*m)

其实算法这种东西，代码不是很重要，重要的是思维。你实现的方式有很多种，但是思维和方法能想到一个就不错了。

3. 案例三：二维数组 DP


摘自Leelcode-64题；

1. 定义数组元素的含义：你要求什么

由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，最小的路径和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我们要的答案了。

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

2. 找出数组元素之间的关系式：往后退一步

往后退一步，要怎么样才能走到 (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] 表示网格中的值
3. 找出初始值：公式求不出的值

谁求不出？i和j中有一个为零都不行，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。

这里的0….m-1可以换算成1...m，也就是1到i，这里分析出来的dp[0….m-1] [0]就是你代码中要代入公式初始化写在左边的。

因此初始值如下：

  • dp[0] [j] = arr[0] [j] + dp[0] [j-1];
  • dp[i] [0] = arr[i] [0] + dp[i-1] [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];
}

4. 案例四：编辑距离

来源：Leelcode-72. 编辑距离;

问题描述：
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符 
示例：
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

让我们来干掉这一题：

90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。

1. 定义数组元素的含义：你要求什么

我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。

2. 找出数组元素之间的关系式：往后退一步

接下来我们就要找 dp[i] [j] 元素之间的关系了，比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。

这里先把题目的条件拉过来：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

还有第一步我们分析的结果：

当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。

也就是说：

  • 如果是在字符串word1末尾插入一个与 word2[j] 相等的字符就能使它符合条件,(注意这里的word1是字符串,word2[j]是字符),那么在这个操作之前，word1后面肯定是少一个字母的，所以将 word1 转化为 word2 所使用的最少操作次数应该是将 后面少一个字母的word1 转化为 word2 所使用的最少操作次数再加上本次操作，也就是加1，翻译成代码就是：dp[i] [j] = dp[i-1] [j] + 1；因为i-1代表的是长度嘛；
  • 如果是在字符串word1末尾删除一个字符就能使它符合条件,那么在这个操作之前，word1后面肯定是多一个字母的，所以将 word1 转化为 word2 所使用的最少操作次数应该是将 后面多一个字母的word1 转化为 word2 所使用的最少操作次数再加上本次操作，也就是加1，翻译成代码就是：dp[i] [j] = dp[i] [j-1] + 1；
  • 如果把字符 word1[i] 替换成与 word2[j] 相等，意思就是将这两个字符串的最后一个字符交换一下就可以了，那交换之前呢？交换之前的最少操作此时肯定是dp[i-1][j-1]，因为我们忽略了最后一个元素了，所以翻译成代码就是：dp[i] [j] = dp[i-1] [j-1] + 1;

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

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

于是，我们的关系式就推出来了。

3. 找出初始值：公式求不出的值

看看哪个是公式求不出的，i和j两个都不能等于0,所以求不出的就是他俩有一个等于零的时候，也就是所有的dp[0] [0….n] 和所有的 dp[0….m] [0]；

这里的0….m-1可以换算成1...m，也就是1到i，这里分析出来的dp[0….m-1] [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)){
                dp[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];  
}

如果你要练习，可以去 leetcode，选择动态规划专题，然后连续刷几十道，保证你以后再也不怕动态规划了。当然，遇到很难的，咱该挂的还是得挂。

OKOKOKOKOOKOKOKOKOKOKOKOKOKOKOKOKOKOKOKOKOKOKOK

到现在为止你已经是一名动态规划初级选手了，要想进阶到中级选手必须充钱
[狗头]。

开玩笑的，要想进阶必须学习油画 ！！！
呸，优化。

另一种思路

好了，我相信这种思路你已经掌握了，我们还有另一种思路解决问题，就是我在前面提到的——两种方法：

  • 自顶向下的备忘录法
  • 自底向上的动态规划

我们前面用到的三大步骤都是：自底向上的动态规划。

你可以用备忘录法自己实现一下，这里就不展开了，留给你自己做。

三、动态规划的经典模型

1. 线性模型

线性模型的是动态规划中最常用的模型，这里的线性指的是状态的排布是呈线性的。我们常用一维数组解题。具体的概念就不展开了，感兴趣的可以再去Google一下什么是线性模型。

2. 区间模型

区间模型基本就是二维空间模型，我们常用二维数组解题，就像我们前面的案例二到案例四都是区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i,j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

3. 背包模型：（较难，可跳过）

背包问题是动态规划中一个最典型的问题之一。

前两个模型我们都有讲到，但是背包模型还没有提到，那么现在我们对背包模型进行详细的讲解。

我们这里用最简单的例子来解决背包问题：

这里使用动态转移方程：
这里第一次提这个概念，相信你也听到过这个概念，你可能也会感到奇怪为什么文章中自始至终都没有提呢，到最后才说？

因为我本人不太喜欢用这个词语，不过它的使用我已经体现过了，其实他就是我们求得 数组元素之间的关系式 再加上 初始值，把这两个式子结合起来就是所谓的动态转移方程。

我觉得吧，关键是理解，他叫什么不重要，你看，我不跟你说什么是动态转移方程也就那么着，你也不会去想他是什么，只要你理解了，无论用什么方法只要能做出来题目，我们的目的也就达到了。

我们这里直接给出背包的状态转换方程：

  • 先确定含义：m[i,W]表示在前i件物品中选择若干件放在承重为 W 的背包中，可以取得的最大价值。
  • Vi表示第i件物品的价值。
  • 决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？


问题描述：
假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。

也就是说有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

  • 只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。
  • 这张表是至底向上，从左到右生成的。
  • 为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
  • 对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
  • 同理，c2=0，b2=3,a2=6。
  • 对于承重为8的背包，a8=15,是怎么得出的呢？

根据01背包的状态转换方程，需要考察两个值：

一个是：

另一个是：

  • m[i-1,W]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
  • m[i-1,W-wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
  • m[i-1,W-wi]就是指单元格b6,值为9，vi指的是a物品的价值，即6
  • 由于m[i-1,W-wi]+vi = 9 + 6 = 15 大于m[i-1,W]= 9，所以物品a应该放入承重为8的背包

好，就讲到这，代码也不给了，感兴趣的自己可以去查阅相关书籍资料。

背包问题有很多特别难的题目，我们浅尝辄止，毕竟只是入门。

三、动态规划的优化

Q：那我该咋优化呢？
A：当然是画图了

没错，80% 的动态规划题都可以画图，其中 80% 的题都可以通过画图一下子知道怎么优化，当然，DP 也有一些很难的题，想优化可没那么容易，不过，今天我要讲的，是属于不怎么难，且最常见，面试笔试最经常考的难度的题。

优化案例

1. 案例一：最多路径数

也就是第二章节的案例二，如果你懒得翻，好吧，我贴在下面：

这道题的 dp 转移公式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

代码实现：

public static int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n];
    
    // 初始化
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
    // 推导出 dp[m-1][n-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];
        }
    }
    return dp[m-1][n-1];
}

我们当时是这个亚子实现的，不过他的空间复杂度是O(n * m)，是可以优化的：

优化案例一

首先dp[i] [j] 是一个二维矩阵，我们来画个二维矩阵的图，对矩阵进行初始化

// 初始化
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
1 1 1 1
1 * * *
1 * * *
1 * * *

然后根据公式 dp[i][j] = dp[i-1][j] + dp[i][j-1] 来填充矩阵的其他值。下面我们先填充第二行的值。

1 1 1 1
1 2 3 4
1 * * *
1 * * *

当我们要填充第三行的值的时候，我们需要用到第一行的值吗？答是不需要的，当你要填充第三，第四…第 n行的时候，第一行的值永远不会用到，只要填充第二行的值时会用到。

根据公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]，我们可以知道，当我们要计算第 i 行的值时，除了会用到第 i-1 行外，其他第 1 至 第 i-2 行的值我们都是不需要用到的，那对于那部分用不到的值我们还有必要保存他们吗？

没必要，我们只需要用一个一维的 dp[] 来保存一行的历史记录就可以了。然后在计算的过程中，不断的更新 dp[] 的值。

估计你可能不好理解，下面我就手把手来演示下这个过程。

  1. 刚开始初始化第一行，此时 dp[0…n-1] 的值就是第一行的值。 
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
1 1 1 1
* * * *
* * * *
* * * *
  1. 接着我们来一边填充第二行的值一边更新 dp[i] 的值，一边把第一行的值抛弃掉。

为了方便描述，下面我们用arr (i，j)表示矩阵中第 i 行 第 j 列的值。从 0 开始，就是说有第 0 行。

  • 显然，矩阵(1, 0) 的值相当于以往的初始化值，为 1。然后这个时候矩阵 (0，0）的值不在需要保存了，因为再也用不到了。
* 1 1 1
1 * * *
* * * *
* * * *
  • 这个时候，我们也要跟着更新 dp[0] 的值了，刚开始 dp[0] = (0, 0)，现在更新为 dp[0] = (1, 0) 。 
dp[0] = 1; //第二行的第一个元素
  • 接着继续更新 (1, 1) 的值，根据之前的公式 （i, j）= (i-1, j) + (i, j- 1)。即 （1，1）=（0，1）+（1，0）=2。
* 1 1 1
1 2 * *
* * * *
* * * * 
dp[0] = 1;
dp[1] = 1; --> dp[1] = 2; //根据公式更新,由第一行转到第二行,第一行的抛弃掉

以往的二维的时候， dp[i][j] = dp[i-1] [j]+ dp[i][j-1]。现在转化成一维，不就是 dp[i] = dp[i] + dp[i-1] 吗？

即 dp[1] = dp[1] + dp[0]，而且还动态帮我们更新了 dp[1] 的值。因为刚开始 dp[i] 的保存第一行的值的，现在更新为保存第二行的值。

* * 1 1
1 2 * *
* * * *
* * * *
  1. 同样的道理，按照这样的模式一直来计算第二行的值，顺便把第一行的值抛弃掉，结果如下：
* * * *
1 2 3 4
* * * *
* * * * 
//由第二行更新至第一行
dp[0] = 1;
dp[1] = 2;
dp[2] = 3;
dp[3] = 4;

此时，dp[i] 将完全保存着第二行的值，并且我们可以推导出公式：

dp[i] = dp[i-1] + dp[i]
//注意
dp[i-1] 相当于之前的 dp[i-1][j]，dp[i] 相当于之前的 dp[i][j-1]。
  1. 于是按照这个公式不停着填充到最后一行，结果如下：
* * * *
* * * *
* * * *
1 4 10 20

最后 dp[n-1] 就是我们要求的结果了。所以优化之后，代码如下：

public static int uniquePaths(int m, int n) {

    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[] dp = new int[n]; 
    
    // 初始化
    for(int i = 0; i < n; i++){
      dp[i] = 1;
    }

    for (int i = 1; i < m; i++) {
    
        // 第 i 行第 0 列的初始值
        dp[0] = 1;
        
        // 公式：dp[i] = dp[i-1] + dp[i]
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j-1] + dp[j];
        }
    }
    return dp[n-1];
}

2. 案例二：编辑距离

也就是第二章节的案例四，如果你懒得翻，好吧，我也贴在下面：

代码实现：

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)){
                dp[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];  
}

这道题的关系式是：
dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;

优化案例二
  • 对于这道题其实也是一样的，如果要计算 第 i 行的值，我们最多只依赖第 i-1 行的值，不需要用到第 i-2 行及其以前的值，所以一样可以采用一维 dp 来处理的。
  • 不过这个时候要注意，在上面的例子中，我们每次更新完 (i, j) 的值之后，就会把 (i, j-1) 的值抛弃，也就是说之前是一边更新 dp[i] 的值，一边把 dp[i] 的旧值抛弃的，不过在这道题中则不可以，因为我们还需要用到它。
  1. 当我们要计算图中 (i,j) 的值的时候，在案例1 中，我们值需要用到 (i-1, j) 和 (i, j-1)。（看图中方格的颜***r>
  2. 不过这道题中，我们还需要用到 （i-1, j-1) 这个值（但是这个值在以往的案例1 中，它会被抛弃掉）

    所以呢，对于这道题，我们还需要一个额外的变量 pre 来时刻保存 (i-1,j-1) 的值。推导公式就可以从二维的 
dp[i][j] = min(dp[i-1][j] , dp[i-1][j-1] , dp[i][j-1]) + 1

转化为一维的

dp[i] = min(dp[i-1], pre, dp[i]) + 1

所以呢，案例2 其实和案例1 差别不大，就是多了个变量来临时保存。

最终代码如下：

代码实现：

public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[] dp = new int[n2 + 1];
    
    // dp[0...n2]的初始值
    for (int j = 0; j <= n2; j++) 
        dp[j] = j;
        
    // dp[j] = min(dp[j-1], pre, dp[j]) + 1
    for (int i = 1; i <= n1; i++) {
        int temp = dp[0];
        // 相当于初始化
        dp[0] = i;
        
        for (int j = 1; j <= n2; j++) {
            // pre 相当于之前的 dp[i-1][j-1]
            int pre = temp;
            temp = dp[j];
            
            // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                dp[j] = pre;
            }else {
               dp[j] = Math.min(Math.min(dp[j - 1], pre), dp[j]) + 1;
            } 
            // 保存要被抛弃的值 
        }
    }
    return dp[n2]; 
}

四、总结

1. 解法总结

为什么动态规划的解法看起来如此精妙，是因为动态规划遵循一套固定的流程：

  • 递归的暴力解法
  • 带备忘录的递归解法
  • 非递归的动态规划解法（关键）

用我们的方法就是：

  • 定义数组元素的含义
  • 找出数组元素之间的关系式
  • 找出初始值

通俗一点就是：

  • 你要求什么
  • 往后退一步
  • 公式求不出的值

2. 作者总结

上面的这些题，基本都是不怎么难的入门题，除了最后一道相对难一点。并且基本 80% 的二维矩阵 dp 都可以像上面的方法一样优化成一维矩阵的dp，核心就是要画图，看他们的值依赖，当然，还有很多其他比较难的优化，但是，我遇到的题中，大部分都是我上面这种类型的优化。

所以说，看完我写的这篇文章是一个什么水平呢？毫不夸张的说，你对于动态规划乃至于算法已经入门了，恭喜，以后还有更多更难的题目等着你，更多关于技术的分享文章，请点击。

最后谢谢你的观看。

参考文章：
1、力扣：72.编辑距离
2、力扣：62.不同路径
3、动态规划套路详解
4、算法-动态规划 Dynamic Programming–从菜鸟到老鸟
5、告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我
6、动态规划之01背包问题（最易理解的讲解）
7、0-1背包问题的动态规划算法