动态规划 | 编辑距离总结

判断子序列

题目 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

可以使用双指针解决。
这道题使编辑距离的入门题目，可以使用动态规划，因为从题意中可以发现，只需要计算删除的情况，不需要考虑增加和替换的情况。

• if (s[i - 1] == t[j - 1])
  t中找到了一个字符在s中也出现了
• if (s[i - 1] != t[j - 1])
  相当于t要删除元素，继续匹配

状态转移方程：

if (s.charAt(i-1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];

不同的子序列

题目 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

本题也只有删除操作，不用考虑增加之类的，但是相对于 判断子序列 有难度。

• 当s[i-1] 与 t[j-1] 相等时，dp[i][j]可以有两部分组成。

  • 一部分是用s[i-1]来匹配，那么个数为 dp[i-1][j-1]

  • 一部分不用是s[i-1]来匹配，个数为dp[i-1][j]

  • 举例说明：s: bagg 和 t: bag，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
    当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

  • 所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

• 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

  • 所以递推公式为：dp[i][j] = dp[i - 1][j]

状态转移方程：

if (s.charAt(i-1) == t.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
    dp[i][j] = dp[i - 1][j];
}

两个字符串的删除操作

题目 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。

本题和 不同子序列 相比，其实就是两个字符串都可以删除了，情况虽说复杂了，但整体思路不变。

• 当word1[i-1] 和 word2[j-1]相同的时候
  • dp[i][j] = dp[i-1][j-1]
• 不同的时候，有三种情况
  • 一：删除word1[i-1] 和 word2[j-1]，最少操作数：dp[i-1][j-1] + 2
  • 二：删除word1[i-1]，最少操作数：dp[i-1][j] + 1， 因为word1[i-2]和 word2[j-1]已经由 dp[i-1][j] 确定，所以 + 1 即可确定操作数，下面同理
  • 三：删除word2[j-1]，最少操作数：dp[i][j-1] + 1
  • 最后取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

状态转移方程：

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
} else {
    dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
}

编辑距离

题目 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

有了前面三道题目的铺垫，应该有思路了，本题是两个字符串可以增删改，比 动态规划：判断子序列，动态规划：不同的子序列，动态规划：两个字符串的删除操作都要复杂的多。

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

• if (word1[i - 1] == word2[j - 1])
  • 不操作
• if (word1[i - 1] != word2[j - 1])
  • 增
  • 删
  • 换

也就是如上四种情况。

• if (word1[i - 1] == word2[j - 1])
  • 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
• if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？
  • 操作一：word1增加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。
    即 dp[i][j] = dp[i - 1][j] + 1;
  • 操作二：word2增加一个元素，使其word1[i-1]与word2[j-1]相同，那么就是以下标i-1为结尾的word1 与 j-2 为结尾的word2的最近编辑距离 加上一个增加元素的操作。
    即 dp[i][j] = dp[i][j-1] + 1;
    里有同学发现了，怎么都是添加元素，删除元素去哪了。
    word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！
  • 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j-1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑举例 加上一个替换元素的操作。
    即 dp[i][j] = dp[i-1][j-1] + 1

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

状态转移方程：

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
}
else {
    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}