1. 什么是动态规划

从数学的视角来看，动态规划是一种运筹学方法，是在多轮决策过程中的最优方法。

那么，什么是多轮决策呢？其实多轮决策的每一轮都可以看作是一个子问题。从分治法的视角来看，每个子问题必须相互独立。但在多轮决策中，这个假设显然不成立。这也是动态规划方法产生的原因之一。

2. 最短路径问题

接下来看一个非常典型的例子，最短路径问题。如下图所示：

每个结点是一个位置，每条边是两个位置之间的距离。现在需要求解出一条由 A 到 G 的最短距离是多少。

不难发现，我们需要求解的路线是由 A 到 G，这就意味着 A 要先到 B，再到 C，再到 D，再到 E，再到 F。每一轮都需要做不同的决策，而每次的决策又依赖上一轮决策的结果。

例如，做 D2 -> E 的决策时，D2 -> E2 的距离为 1，最短。但这轮的决策，基于的假设是从 D2 出发，这就意味着前面一轮的决策结果是 D2。由此可见，相邻两轮的决策结果并不是独立的。

动态规划还有一个重要概念叫作状态。在这个例子中，状态是个变量，而且受决策动作的影响。例如，第一轮决策的状态是 S1，可选的值是 A，第二轮决策的状态是 S2，可选的值就是 B1 和 B2。以此类推。

3. 动态规划的基本方法

动态规划问题之所以难，是因为动态规划的解题方法并没有那么标准化，它需要你因题而异，仔细分析问题并寻找解决方案。虽然动态规划问题没有标准化的解题方法，但它有一些宏观层面通用的方法论：

下面的 k 表示多轮决策的第 k 轮

1. 分阶段，将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段，它们可以是不满足独立性的。
2. 找状态，选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变，更像是决策可能的结果。
3. 做决策，确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作，例如 D2 的可能的决策动作是 D2 -> E2 和 D2 ->E3。
4. 状态转移方程。这个步骤是动态规划最重要的核心，即 sk+1= uk(sk) 。
5. 定目标。写出代表多轮决策目标的指标函数 Vk,n。
6. 寻找终止条件。

了解了方法论、状态、多轮决策之后，我们再补充一些动态规划的基本概念。

• 策略，每轮的动作是决策，多轮决策合在一起常常被称为策略。
• 策略集合，由于每轮的决策动作都是一个变量，这就导致合在一起的策略也是一个变量。我们通常会称所有可能的策略为策略集合。因此，动态规划的目标，也可以说是从策略集合中，找到最优的那个策略。

一般而言，具有如下几个特征的问题，可以采用动态规划求解：

1. 最优子结构。它的含义是，原问题的最优解所包括的子问题的解也是最优的。例如，某个策略使得 A 到 G 是最优的。假设它途径了Fi，那么它从 A 到 Fi 也一定是最优的。
2. 无后效性。某阶段的决策，无法影响先前的状态。可以理解为今天的动作改变不了历史。
3. 有重叠子问题。也就是，子问题之间不独立。这个性质是动态规划区别于分治法的条件。如果原问题不满足这个特征，也是可以用动态规划求解的，无非就是杀鸡用了宰牛刀。

4. 案例

到这里，动态规划的概念和方法就讲完了。接下来，我们以最短路径问题再来看看动态规划的求解方法。在这个问题中，你可以采用最暴力的方法，那就是把所有的可能路径都遍历一遍，去看哪个结果的路径最短的。如果采用动态规划方法，那么我们按照方法论来执行。

4.1 动态规划的求解方法
具体的解题步骤如下：

• 分阶段 很显然，从 A 到 G，可以拆分为 A -> B、B -> C、C -> D、D -> E、E -> F、F -> G，6
  个阶段。

• 找状态
  第一轮的状态 S1 = A，第二轮 S2 = {B1,B2}，第三轮 S3 = {C1,C2,C3,C4}，第四轮 S4 = {D1,D2,D3}，第五轮 S5 = {E1,E2,E3}，第六轮 S6 = {F1,F2}，第七轮 S7 = {G}。

• 做决策
  决策变量就是上面图中的每条边。我们以第四轮决策 D -> E 为例来看，可以得到 u4(D1)，u4(D2)，u4(D3)。其中 u4(D1) 的可能结果是 E1 和 E2。

• 写出状态转移方程
  在这里，就是 sk+1 = uk(sk)。

• 定目标
  别忘了，我们的目标是总距离最短。我们定义 dk(sk,uk) 是在 sk 时，选择 uk 动作的距离。例如，d5(E1,F1) = 3。那么此时 n = 7，则有，
  $$v_{k,7}\left(s_1=A,s_7=G\right)=\sum _{k=1}^7{d}_k\left(s_k,u_k\right)$$
  就是最终要优化的目标。

• 寻找终止条件

• 很显然，这里的起止条件分别是，s1 = A 和 s7 = G。

• 接下来，我们把所有的已知条件，凝练为上面的符号之后，只需要借助最优子结构，就可以把问题解决了。最优子结构的含义是，原问题的最优解所包括的子问题的解也是最优的。

• 套用在这个例子的含义就是，如果 A -> … -> F1 -> G 是全局 A 到 G 最优的路径，那么此处 A -> … ->
  F1 也是 A 到 F1 的最优路径。

• 因此，此时的优化目标 min Vk,7(s1=A, s7=G)，等价于 min { Vk,6(s1=A, s6=F1)+4，
  Vk,6(s1=A, s6=F2)+3 }。

• 此时，优化目标的含义为，从 A 到 G 的最短路径，是 A 到 F1 到 G 的路径和 A 到 F2 到 G 的路径中更短的那个。

• 同样的，对于上面式子中，Vk,6(s1=A,s6=F1) 和 Vk,6(s1=A,s6=F2)，仍然可以递归地使用上面的分析方法。

4.2 计算过程详解
好了，为了让大家清晰地看到结果，我们给出详细的计算过程。为了书写简单，我们把函数 Vk,7(s1=A, s7=G) 精简为 V7(G)，含义为经过了 6 轮决策后，状态到达 G 后所使用的距离。我们把图片复制到这里一份，方便大家不用上下切换。

我们的优化目标为 min Vk,7(s1=A, s7=G)，因此精简后原问题为，min V7(G)。

因此，最终输出路径为 A -> B1 -> C2 -> D1 -> E2 -> F2 -> G，最短距离为 18。

4.3 代码实现过程
接下来，我们尝试用代码来实现上面的计算过程。对于输入的图，可以采用一个 m x m 的二维数组来保存。在这个二维数组里，m 等于全部的结点数，也就是结点与结点的关系图。而数组每个元素的数值，定义为结点到结点需要的距离。

在本例中，可以定义输入矩阵 m（空白处为0），如下图所示：

代码如下：

public class testpath {
    public static int minPath1(int[][] matrix) {
        return process1(matrix, matrix[0].length-1);
    }
    // 递归
    public static int process1(int[][] matrix, int i) {
        // 到达A退出递归
        if (i == 0) {
            return 0;
        }
        // 状态转移
        else{
            int distance = 999;
            for(int j=0; j<i; j++){
                if(matrix[j][i]!=0){
                    int d_tmp = matrix[j][i] + process1(matrix, j);
                    if (d_tmp < distance){
                        distance = d_tmp;
                    }
                }
            }
            return distance;
        }
    }
    public static void main(String[] args) {
        int[][] m = {{0,5,3,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,3,6,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,8,7,6,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,6,8,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,3,5,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,8,4,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,5,2,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3}};
        System.out.println(minPath1(m));
    }
}

代码解读：

代码的 27 行是主函数，在代码中定义了二维数组 m，对应于输入的距离图。m 是 15 x 16 维的，我们忽略了最后一行的全 0（即使输入也不会影响结果）。

然后调用函数 minPath1。在第 2 到第 4 行，它的内部又调用了 process1(matrix, matrix[0].length-1)。在这里，matrix[0].length-1 的值是 15，表示的含义是 matrix 数组的第 16 列（G）是目的地。

接着进入 process1 函数中。我们知道在动态规划的过程中，是从后往前不断地推进结果，这就是状态转移的过程。对应代码中的 13-24 行：

• 第 15 行开始循环，j 变量是纵向的循环变量。
• 第 16 行判断 matrix[j][i] 与 0 的关系，含义为，只有值不为 0 才说明两个结点之间存在通路。
• 一旦发现某个通路，就需要计算其距离。计算的方式是 17 行的
  d_tmp = matrix[j][i] + process1(matrix, j)
• 当得到了距离之后，还需要找到最短的那个距离，也就是 18 到 20 行的含义。这就是动态规划最优子结构的体现。
• 一旦 i 减小到了 0，就说明已经到了起点 A。那么 A 到 A 的距离就是 0，直接第 10 行的 return 0 就可以了。
• 经过运行，这段代码的输出结果是 18，这与我们手动的推导结果一致。
  本文参考拉钩教育学习视频

动态规划难吗？说实话，我觉得很难，特别是对于初学者来说，我当时入门动态规划的时候，是看 0-1 背包问题，当时真的是一脸懵逼。后来，我遇到动态规划的题，看的懂答案，但就是自己不会做，不知道怎么下手。就像做递归的题，看的懂答案，但下不了手，关于递归的，我之前也写过一篇套路的文章，如果对递归不大懂的，强烈建议看一看：为什么你学不会递归，告别递归，谈谈我的经验

对于动态规划，春招秋招时好多题都会用到动态规划，一气之下，再 leetcode 连续刷了几十道题

之后，豁然开朗 ，感觉动态规划也不是很难，今天，我就来跟大家讲一讲，我是怎么做动态规划的题的，以及从中学到的一些套路。相信你看完一定有所收获

如果你对动态规划感兴趣，或者你看的懂动态规划，但却不知道怎么下手，那么我建议你好好看以下，这篇文章的写法，和之前那篇讲递归的写法，是差不多一样的，将会举大量的例子。如果一次性看不完，建议收藏，同时别忘了素质三连。

为了兼顾初学者，我会从最简单的题讲起，后面会越来越难，最后面还会讲解，该如何优化。因为 80% 的动规都是可以进行优化的。不过我得说，如果你连动态规划是什么都没听过，可能这篇文章你也会压力山大。

一、动态规划的三大步骤

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

如果你听不懂，也没关系，下面会有很多例题讲解，估计你就懂了。之所以不配合例题来讲这些步骤，也是为了怕你们脑袋乱了

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 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.

三个步骤都做出来了，那么我们就来写代码吧，代码会详细注释滴。

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

（4）、再说初始化

大家先想以下，你觉得，上面的代码有没有问题？

答是有问题的，还是错的，错在对初始值的寻找不够严谨，这也是我故意这样弄的，意在告诉你们，关于初始值的严谨性。例如对于上面的题，当 n = 2 时，dp[2] = dp[1] + dp[0] = 1。这显然是错误的，你可以模拟一下，应该是 dp[2] = 2。

也就是说，在寻找初始值的时候，一定要注意不要找漏了，dp[2] 也算是一个初始值，不能通过公式计算得出。有人可能会说，我想不到怎么办？这个很好办，多做几道题就可以了。

下面我再列举三道不同的例题，并且，再在未来的文章中，我也会持续按照这个步骤，给大家找几道有难度且类型不同的题。下面这几道例题，不会讲的特性详细哈。实际上 ，上面的一维数组是可以把空间优化成更小的，不过我们现在先不讲优化的事，下面的题也是，不讲优化版本。

案例二：二维数组的 DP

我做了几十道 DP 的算法题，可以说，80% 的题，都是要用二维数组的，所以下面的题主要以二维数组为主，当然有人可能会说，要用一维还是二维，我怎么知道？这个问题不大，接着往下看。

问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

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

这是 leetcode 的 62 号题：https://leetcode-cn.com/problems/unique-paths/

还是老样子，三个步骤来解决。

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 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; // 相当于最左面一列，机器人只能一直往下走

撸代码

三个步骤都写出来了，直接看代码

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(min(n, m)) 的空间复杂度的，不过这里先不讲

案例三、二维数组 DP

写到这里，有点累了，，但还是得写下去，所以看的小伙伴，你们可得继续看呀。下面这道题也不难，比上面的难一丢丢，不过也是非常类似

问题描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

举例：
输入:
arr = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

和上面的差不多，不过是算最优路径和，这是 leetcode 的第64题：https://leetcode-cn.com/problems/minimum-path-sum/

还是老样子，可能有些人都看烦了，哈哈，但我还是要按照步骤来写，让那些不大懂的加深理解。有人可能觉得，这些题太简单了吧，别慌，小白先入门，这些属于 medium 级别的，后面在给几道 hard 级别的。

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 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]; // 相当于最左面一列，机器人只能一直往下走

代码如下

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];
}

O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的，不过这里先不讲

案例 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 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。

代码如下

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];  
}

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

Leetcode 动态规划直达：https://leetcode-cn.com/tag/dynamic-programming/

三、总结

上面的这些题，基本都是不怎么难的入门题，除了最后一道相对难一点，本来是要在写几道难一点，并且讲如何优化的，不过看了下字数，文章有点长了，关于如何优化的，后面再讲吧，在之后的文章中，我也会按照这个步骤，在给大家讲四五道动态规划 hard 级别的题，会放在每天推文的第二条给大家学习。如果大家感兴趣，文章看的人多，那么优化篇很快就会撸出来，大家想要第一时间观看我的文章的，可以关注我的个人微信公众号『苦逼的码农』，不过感兴趣的人很少的话，动力比较少，可能就会慢一些，所以各位小伙伴，如果觉得有收获，不放三连走起来，嘻嘻。

有收获？希望老铁们来个三连击，给更多的人看到这篇文章

1、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。

2、老铁们，关注我的原创微信公众号「帅地玩编程」，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux）。

保存让你看完有所收获，不信你打我。后台回复『电子书』送你一份精选电子书大礼包，包含各类技能的优质电子书。