# 动态规划
### 一、动态规划的三大步骤
动态规划，无非就是利用**历史记录**，来避免我们的重复计算。而这些**历史记录**，我们得需要一些**变量**来保存，一般是用**一维数组**或者**二维数组**来保存。下面我们先来讲下做动态规划题很重要的三个步骤，
**第一步骤**：定义**数组元素的含义**，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp\[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp\[i] 是代表什么意思？
**第二步骤**：找出**数组元素之间的关系式**，我觉得动态规划，还是有一点类似于我们高中学习时的**归纳法**的，当我们要计算 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]，我们可以通过 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] 的含义是由你来定义的，你想**求什么，就定义它是什么**，这样，这道题也就解出来了。
### 二、案例详解
### 案例一、简单的一维 DP
> 问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
### (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 级跳上来
由于我们是要算**所有可能的跳法的**，所以有 dp\[n] = dp\[n-1] + dp\[n-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.
三个步骤都做出来了，那么我们就来写代码吧。
```
func my(n int) int {
if n < 2 {
return 1
}
var bp = make([]int, n+1)
bp[0], bp[1] = 1, 1
for i := 2; i <= n; i++ {
bp[i] = (bp[i-1] + bp[i-2])%(1e9 + 7)//提前取模，防止溢出
}
return bp[n]
}
```
### 案例二：二维数组的 DP
80% 的题，都是要用二维数组的，所以下面的题主要以二维数组为主，当然有人可能会说，要用一维还是二维，我怎么知道？这个问题不大，接着往下看。
### 问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
还是老样子，三个步骤来解决。
### 步骤一、定义数组元素的含义
由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp\[i] \[j]的含义为：**当机器人从左上角走到(i, j) 这个位置时，一共有 dp\[i] \[j] 种路径**。那么，dp\[m-1] \[n-1] 就是我们要的答案了。
> 注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以 右下角的位置是 (m-1, n - 1)，所以 dp\[m-1] \[n-1] 就是我们要找的答案。
### 步骤二：找出关系数组元素间的关系式
想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp\[i] \[j] = dp\[i-1] \[j] + dp\[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] \[0….n-1] = 1; // 相当于最上面一行，机器人只能一直往左走
dp\[0…m-1] \[0] = 1; // 相当于最左面一列，机器人只能一直往下走
### 代码
三个步骤都写出来了，直接看代码
```
func my(m int, n int) int {
if m == 1 || n == 1 {
return 1
}
var bp = make([][]int, m*n)
for i := 0; i < m; i++ {
bp[i] = make([]int, n)
}
for i := 0; i < m; i++ {
bp[i][0] = 1
}
for j := 1; j < n; j++ {
bp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
bp[i][j] = bp[i-1][j] + bp[i][j-1]
}
}
return bp[m-1][n-1]
}
```
> O(n\*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的，不过这里先不讲
### 案例三、二维数组 DP
### 问题描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
```
举例：
输入:
arr = [
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→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] 就是我们要走的答案。
### 步骤二：找出关系数组元素间的关系式
想象以下，机器人要怎么样才能到达 (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] 表示网格种的值
```
### 步骤三、找出初始值
显然，当 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]; // 相当于最左面一列，机器人只能一直往下走
### 代码如下
```
func my(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dp = make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i := 1; i < n; i++ {
dp[0][i] = dp[0][i-1] + grid[0][i]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i][j-1] + grid[i][j]
} else {
dp[i][j] = dp[i-1][j] + grid[i][j]
}
}
}
return dp[m-1][n-1]
}
```
### 案例 4：编辑距离
这次给的这道题比上面的难一些，在 leetcdoe 的定位是 hard 级别。好像是 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 进行三种操作**
`插入一个字符` `删除一个字符` `替换一个字符`
由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式：
一、如果我们 word1\[i] 与 word2 \[j] 相等，这个时候不需要进行任何操作，显然有 dp\[i] \[j] = dp\[i-1] \[j-1]。（别忘了 dp\[i] \[j] 的含义哈）。
二、如果我们 word1\[i] 与 word2 \[j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
（1）、如果把字符 word1\[i] 替换成与 word2\[j] 相等，则有 dp\[i] \[j] = dp\[i-1] \[j-1] + 1;
（2）、如果在字符串 word1末尾插入一个与 word2\[j] 相等的字符，则有 dp\[i] \[j] = dp\[i] \[j-1] + 1;
（3）、如果把字符 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 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。
### 代码如下
```
func my(word1 string, word2 string) int {
len1, len2 := len(word1), len(word2)
if len1 == 0 || len2 == 0 {
return len1 + len2
}
//当字符串word1的长度为len1，字符串word2的长度为len2时，将word1转化为word2所使用的最少操作次数为dp[len1][len2]
dp := make([][]int, len1+1) //初始化第一维数组，从1开始
for i := range dp {
dp[i] = make([]int, len2+1) //初始化第二维数组，从1开始
}
dp[0][1], dp[1][0], dp[1][1] = 1, 1, 1 //预初始化基本值，因为下面循环在len为1时不会进入
for i := 1; i < len1+1; i++ {
dp[i][0] = dp[i-1][0] + 1 //每次字符串长度加一，就相当于添加一个字符，因此需要加一步
}
for j := 1; j < len2+1; j++ {
dp[0][j] = dp[0][j-1] + 1
}
for i := 1; i <= len1; i++ {
for j := 1; j <= len2; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1] //字符相等，不需要进行操作
} else {
dp[i][j] = int(math.Min(float64(dp[i-1][j-1]), math.Min(float64(dp[i-1][j]), float64(dp[i][j-1])))) + 1 //多出一步运算
}
}
}
return dp[len1][len2]
}
```
最后说下，如果你要练习，可以去 leetcode，选择动态规划专题，然后连续刷几十道，保证你以后再也不怕动态规划了。
Leetcode 动态规划直达：[https://leetcode-cn.com/tag/dynamic-programming/](https://link.zhihu.com/?target=https%3A//leetcode-cn.com/tag/dynamic-programming/)
### 三、优化核心：画图！画图！画图
没错，80% 的动态规划题都可以画图，其中 80% 的题都可以通过画图一下子知道怎么优化，当然，DP 也有一些很难的题，想优化可没那么容易，不过，今天我要讲的，是属于不怎么难，且最常见，面试笔试最经常考的难度的题。
下面我们直接通过三道题目来讲解优化，你会发现，这些题，优化过后，代码只有细微的改变，你只要会一两道，可以说是会了 80% 的题。
### O(n\*m) 空间复杂度优化成 O(n)
上次那个青蛙跳台阶的 dp 题是可以把空间复杂度 O( n) 优化成 O(1)，本来打算从这道题讲起的，但想了下，想要学习 dp 优化的感觉至少都是 **小小大佬**了，所以就不讲了，就从二维数组的 dp 讲起。
### 案例1：最多路径数
### 问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
> 这是 leetcode 的 62 号题：[https://leetcode-cn.com/problems/unique-paths/](https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/unique-paths/)
这道题的 dp 转移公式是 dp\[i] \[j] = dp\[i-1] \[j] + dp\[i] \[j-1]，代码如下
> 不懂的看我之前文章：[告别动态规划，连刷40道动规算法题，我总结了动规的套路](https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s/pg-IJ8rA1duIzt5hW1Cycw)
```
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)，下面我们来讲解如何优化成 O(n)。
dp\[i] \[j] 是一个二维矩阵，我们来画个二维矩阵的图，对矩阵进行初始化
然后根据公式 dp\[i]\[j] = dp\[i-1]\[j] + dp\[i]\[j-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] 的值就是第一行的值。
2、接着我们来一边填充第二行的值一边更新 dp\[i] 的值，一边把第一行的值抛弃掉。
> 为了方便描述，下面我们用arr (i，j）表示矩阵中第 i 行 第 j 列的值。从 0 开始哈，就是说有第 0 行。
（1）、显然，矩阵(1, 0) 的值相当于以往的初始化值，为 1。然后这个时候矩阵 (0，0）的值不在需要保存了，因为再也用不到了。
这个时候，我们也要跟着更新 dp\[0] 的值了，刚开始 dp\[0] = (0, 0)，现在更新为 dp\[0] = (1, 0)。
（2）、接着继续更新 (1, 1) 的值，根据之前的公式 （i, j) = (i-1, j) + (i, j- 1)。即 （1，1）=（0，1）+（1，0）=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] 的保存第一行的值的，现在更新为保存第二行的值。
(3)、同样的道理，按照这样的模式一直来计算第二行的值，顺便把第一行的值抛弃掉，结果如下
此时，dp\[i] 将完全保存着第二行的值，并且我们可以推导出公式
dp\[i] = dp\[i-1] + dp\[i]
> dp\[i-1] 相当于之前的 dp\[i-1]\[j]，dp\[i] 相当于之前的 dp\[i]\[j-1]。
于是按照这个公式不停着填充到最后一行，结果如下：
最后 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;
}
// 公式：dp[i] = dp[i-1] + dp[i]
for (int i = 1; i < m; i++) {
// 第 i 行第 0 列的初始值
dp[0] = 1;
for (int j = 1; j < n; j++) {
dp[j] = dp[j-1] + dp[j];
}
}
return dp[n-1];
}
```
### 案例2：编辑距离
接着我们来看昨天的另外一道题，就是**编辑矩阵**，这道题的优化和这一道有一点点的不同，上面这道 dp\[i]\[j] 依赖于 dp\[i-1]\[j] 和 dp\[i]\[j-1]。而还有一种情况就是 dp\[i]\[j] 依赖于 dp\[i-1]\[j]，dp\[i-1]\[j-1] 和 dp\[i]\[j-1]。
**问题描述**
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
```
示例：
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
```
**解答**
昨天的代码如下所示，不懂的记得看之前的文章哈：[告别动态规划，连刷40道动规算法题，我总结了动规的套路](https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s/pg-IJ8rA1duIzt5hW1Cycw)
```
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];
}
```
> 没有优化之间的空间复杂度为 O(n\*m)
大家可以自己动手做下，按照上面的那个模式，你会优化吗？
对于这道题其实也是一样的，如果要计算 第 i 行的值，我们最多只依赖第 i-1 行的值，不需要用到第 i-2 行及其以前的值，所以一样可以采用一维 dp 来处理的。
不过这个时候要注意，在上面的例子中，我们每次更新完 (i, j) 的值之后，就会把 (i, j-1) 的值抛弃，也就是说之前是一边更新 dp\[i] 的值，一边把 dp\[i] 的旧值抛弃的，不过在这道题中则不可以，因为我们还需要用到它。
哎呀，直接举例子看图吧，文字绕来绕去估计会绕晕你们。当我们要计算图中 (i,j) 的值的时候，在案例1 中，我们值需要用到 (i-1, j) 和 (i, j-1)。（看图中方格的颜色）
不过这道题中，我们还需要用到 （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];
}
```
### 总结
上面的这些题，基本都是不怎么难的入门题，除了最后一道相对难一点。并且基本 80% 的二维矩阵 dp 都可以像上面的方法一样优化成 一维矩阵的 dp，核心就是要画图，看他们的**值依赖**，当然，还有很多其他比较难的优化，但是，我遇到的题中，大部分都是我上面这种类型的优化。后面如何遇到其他的，我会作为案例来讲，今天就先讲**最普遍最通用的优化方案**。记住，画二维 dp 的矩阵图，然后看元素之间的值依赖，然后就可以很清晰着知道该如何优化了。
在之后的文章中，我也会按照这个步骤，在给大家讲四五道动态规划 **hard** 级别的题，会放在每天推文的第二条给大家学习。如果觉得有收获，不放**三连**走起来（点赞、感谢、分享），嘻嘻。