还是老样子，按照上面三个步骤来，并且我这里可以告诉你，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/
三、如何优化？前两天写一篇长达 8000 子的关于动态规划的文章告别动态规划，连刷40道动规算法题，我总结了动规的套路
这篇文章更多讲解我平时做题的套路，不过由于篇幅过长，举了 4 个案例之后，没有讲解优化，今天这篇文章就来讲解下，对动态规划的优化如何下手，并且以前几天那篇文章的题作为例子直接讲优化，如果没看过的建议看一下（不看也行，我会直接给出题目以及没有优化前的代码）：告别动态规划，连刷40道动规算法题，我总结了动规的套路
四、优化核心：画图！画图！画图没错，80% 的动态规划题都可以画图，其中 80% 的题都可以通过画图一下子知道怎么优化，当然，DP 也有一些很难的题，想优化可没那么容易，不过，今天我要讲的，是属于不怎么难，且最常见，面试笔试最经常考的难度的题。
下面我们直接通过三道题目来讲解优化，你会发现，这些题，优化过后，代码只有细微的改变，你只要会一两道，可以说是会了 80% 的题。
O(n*m) 空间复杂度优化成 O(n)上次那个青蛙跳台阶的 dp 题是可以把空间复杂度 O( n) 优化成 O(1)，本来打算从这道题讲起的，但想了下，想要学习 dp 优化的感觉至少都是 小小大佬了，所以就不讲了，就从二维数组的 dp 讲起。
案例1：最多路径数 问题描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？