初始状态：
      ''  r  o  s
   ''  0  1  2  3
   h   1
   o   2
   r   3
   s   4
   e   5

      ''  r  o  s
   ''  0  1  2  3
   h   1  1  2  3
   o   2  2  1  2
   r   3  2  2  2
   s   4  3  3  2
   e   5  4  4 *3*

最小编辑距离（Minimum Edit Distance） 题目描述 给定两个单词 word1 和 word2，找到将 word1 转换成 word2 所需的最少操作次数。允许的操作有以下三种： 插入一个字符 删除一个字符 替换一个字符 示例 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解题过程 我们将使用动态规划来系统地解决这个问题。动态规划的核心思想是 将原问题分解为子问题，并利用子问题的解来构建原问题的解 。 步骤一：定义状态 我们首先需要定义能表示“进度”的状态。一个直观的想法是：考虑 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。 因此，我们定义： dp[i][j] = 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑距离。 i 的范围是 [0, m] ，其中 m = word1.length() 。 i=0 表示 word1 为空字符串。 j 的范围是 [0, n] ，其中 n = word2.length() 。 j=0 表示 word2 为空字符串。 我们的最终目标是求解 dp[m][n] 。 步骤二：状态初始化 这是动态规划的关键步骤，我们需要确定一些基本情况。 dp[0][0] ：两个空字符串相互转换，不需要任何操作。 dp[0][0] = 0 。 dp[i][0] ：将 word1 的前 i 个字符转换为空字符串。唯一的办法是删除这 i 个字符，需要 i 次删除操作。因此， dp[i][0] = i 。 dp[0][j] ：将空字符串转换为 word2 的前 j 个字符。唯一的办法是插入这 j 个字符，需要 j 次插入操作。因此， dp[0][j] = j 。 步骤三：推导状态转移方程 这是最核心的一步。我们考虑如何从已知的更小的子问题 dp[i-1][j-1] ， dp[i][j-1] ， dp[i-1][j] 来推导 dp[i][j] 。 对于 dp[i][j] ，我们关注的是 word1 的第 i 个字符（ word1[i-1] ）和 word2 的第 j 个字符（ word2[j-1] ）。这里下标 i-1 和 j-1 是因为我们的状态定义是“前 i 个字符”，索引从 1 开始，而字符串索引从 0 开始。 情况一：当前两个字符相同 如果 word1[i-1] == word2[j-1] ，那么我们不需要对最后一个字符做任何操作。整个问题的最小编辑距离就等同于前 i-1 个字符转换成前 j-1 个字符的最小编辑距离。 dp[i][j] = dp[i-1][j-1] 情况二：当前两个字符不同 如果 word1[i-1] != word2[j-1] ，我们有三种操作可以选择，我们需要选择 操作次数最少 的那一种： 替换 ：将 word1[i-1] 替换成 word2[j-1] 。这个操作本身花费 1 次。操作完成后，问题就变成了将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符。 所需总操作数为： dp[i-1][j-1] + 1 插入 ：在 word1 的第 i 个位置（即 word1[i-1] 后面）插入一个字符 word2[j-1] 。这个操作本身花费 1 次。插入后， word1 的第 i 个字符（新插入的）已经和 word2[j-1] 匹配了。现在我们需要将 word1 的 i 个字符（原来前 i 个 + 新插入的 1 个）的前 i 个（即原来未变的前 i 个）转换为 word2 的前 j-1 个字符。 所需总操作数为： dp[i][j-1] + 1 这里 dp[i][j-1] 表示将 word1 的前 i 个字符变为 word2 的前 j-1 个字符。理解：我们通过一次插入操作，使目标字符串的匹配长度增加了一位（ j-1 -> j ），而源字符串的长度 i 不变。 删除 ：删除 word1 的第 i 个字符（ word1[i-1] ）。这个操作本身花费 1 次。删除后，我们需要将 word1 剩下的前 i-1 个字符转换为 word2 的前 j 个字符。 所需总操作数为： dp[i-1][j] + 1 这里 dp[i-1][j] 表示将 word1 的前 i-1 个字符变为 word2 的前 j 个字符。理解：我们通过一次删除操作，使源字符串的长度减少了一位（ i -> i-1 ），而目标字符串的长度 j 不变。 对于情况二，我们取这三种操作的最小值： dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1 将情况一和情况二合并 ： 我们可以用一个简洁的式子表示： cost = (word1[i-1] == word2[j-1]) ? 0 : 1 dp[i][j] = min( dp[i-1][j-1] + cost, // 替换或直接匹配 dp[i][j-1] + 1, // 插入 dp[i-1][j] + 1 // 删除 ) 步骤四：确定填表顺序 根据状态转移方程， dp[i][j] 依赖于其 左方 ( dp[i][j-1] )、 上方 ( dp[i-1][j] ) 和 左上方 ( dp[i-1][j-1] ) 的值。 因此，我们可以按行（ i 从 1 到 m）或按列（ j 从 1 到 n）来填充整个 (m+1) x (n+1) 的二维 dp 表。 步骤五：计算与结果 按照上述顺序填充 dp 表。最终，表格右下角的 dp[m][n] 就是我们要求的答案。 以示例 word1 = "horse", word2 = "ros" 进行推演 初始化一个 (5+1) x (3+1) = 6 x 4 的表格。 按行填充： i=1, j=1 : word1[ 0]=’h’, word2[ 0 ]=’r’, 不同 -> cost=1。 dp[ 1][ 1] = min(dp[ 0][ 0]+1, dp[ 1][ 0]+1, dp[ 0][ 1 ]+1) = min(0+1, 1+1, 1+1) = 1 i=1, j=2 : word1[ 0]=’h’, word2[ 1 ]=’o’, 不同 -> cost=1。 dp[ 1][ 2] = min(dp[ 0][ 1]+1, dp[ 1][ 1]+1, dp[ 0][ 2 ]+1) = min(1+1, 1+1, 2+1) = 2 i=1, j=3 : word1[ 0]=’h’, word2[ 2 ]=’s’, 不同 -> cost=1。 dp[ 1][ 3] = min(dp[ 0][ 2]+1, dp[ 1][ 2]+1, dp[ 0][ 3 ]+1) = min(2+1, 2+1, 3+1) = 3 i=2, j=1 : word1[ 1]=’o’, word2[ 0 ]=’r’, 不同 -> cost=1。 dp[ 2][ 1] = min(dp[ 1][ 0]+1, dp[ 2][ 0]+1, dp[ 1][ 1 ]+1) = min(1+1, 2+1, 1+1) = 2 i=2, j=2 : word1[ 1]=’o’, word2[ 1 ]=’o’, 相同 -> cost=0。 dp[ 2][ 2] = min(dp[ 1][ 1]+0, dp[ 2][ 1]+1, dp[ 1][ 2 ]+1) = min(1+0, 2+1, 2+1) = 1 i=2, j=3 : word1[ 1]=’o’, word2[ 2 ]=’s’, 不同 -> cost=1。 dp[ 2][ 3] = min(dp[ 1][ 2]+1, dp[ 2][ 2]+1, dp[ 1][ 3 ]+1) = min(2+1, 1+1, 3+1) = 2 i=3, j=1 : word1[ 2]=’r’, word2[ 0 ]=’r’, 相同 -> cost=0。 dp[ 3][ 1] = min(dp[ 2][ 0]+0, dp[ 3][ 0]+1, dp[ 2][ 1 ]+1) = min(2+0, 3+1, 2+1) = 2 i=3, j=2 : word1[ 2]=’r’, word2[ 1 ]=’o’, 不同 -> cost=1。 dp[ 3][ 2] = min(dp[ 2][ 1]+1, dp[ 3][ 1]+1, dp[ 2][ 2 ]+1) = min(2+1, 2+1, 1+1) = 2 i=3, j=3 : word1[ 2]=’r’, word2[ 2 ]=’s’, 不同 -> cost=1。 dp[ 3][ 3] = min(dp[ 2][ 2]+1, dp[ 3][ 2]+1, dp[ 2][ 3 ]+1) = min(1+1, 2+1, 2+1) = 2 i=4, j=1 : word1[ 3]=’s’, word2[ 0 ]=’r’, 不同 -> cost=1。 dp[ 4][ 1] = min(dp[ 3][ 0]+1, dp[ 4][ 0]+1, dp[ 3][ 1 ]+1) = min(3+1, 4+1, 2+1) = 3 i=4, j=2 : word1[ 3]=’s’, word2[ 1 ]=’o’, 不同 -> cost=1。 dp[ 4][ 2] = min(dp[ 3][ 1]+1, dp[ 4][ 1]+1, dp[ 3][ 2 ]+1) = min(2+1, 3+1, 2+1) = 3 i=4, j=3 : word1[ 3]=’s’, word2[ 2 ]=’s’, 相同 -> cost=0。 dp[ 4][ 3] = min(dp[ 3][ 2]+0, dp[ 4][ 2]+1, dp[ 3][ 3 ]+1) = min(2+0, 3+1, 2+1) = 2 i=5, j=1 : word1[ 4]=’e’, word2[ 0 ]=’r’, 不同 -> cost=1。 dp[ 5][ 1] = min(dp[ 4][ 0]+1, dp[ 5][ 0]+1, dp[ 4][ 1 ]+1) = min(4+1, 5+1, 3+1) = 4 i=5, j=2 : word1[ 4]=’e’, word2[ 1 ]=’o’, 不同 -> cost=1。 dp[ 5][ 2] = min(dp[ 4][ 1]+1, dp[ 5][ 1]+1, dp[ 4][ 2 ]+1) = min(3+1, 4+1, 3+1) = 4 i=5, j=3 : word1[ 4]=’e’, word2[ 2 ]=’s’, 不同 -> cost=1。 dp[ 5][ 3] = min(dp[ 4][ 2]+1, dp[ 5][ 2]+1, dp[ 4][ 3 ]+1) = min(3+1, 4+1, 2+1) = 3 最终 dp 表： 答案为 dp[5][3] = 3 ，与示例一致。 总结 最小编辑距离是一个经典的动态规划问题。通过定义 dp[i][j] 表示子问题的解，初始化边界情况，并利用字符匹配关系推导出状态转移方程，我们可以系统、高效地求解整个问题。