代码随想录动态规划——编辑距离总结篇

判断子序列
判断子序列给定字符串 s 和 t ，判断 s 是否为 t 的子序列，可以用贪心或者双指针，也可以考虑dp（只用计算删除，不用考虑增加和替换的情况）

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

状态转移方程：

if (s[i - 1] == t[j - 1]) 
	dp[i][j] = dp[i - 1][j - 1] + 1;
else 
	dp[i][j] = dp[i][j - 1];
1
2
3
4

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

• 当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成
  （1）使用s[i - 1]，相当于同时消除，个数为dp[i - 1][j - 1]
  （2）不使用s[i - 1]，相当于只消除 s，个数为dp[i - 1][j]
• 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

状态转移方程：

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
    dp[i][j] = dp[i - 1][j];
}
1
2
3
4
5

两个字符串的删除操作
两个字符串的删除操作给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符，本题是两个字符串都可以删除

• 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]

• 当word1[i - 1] 与 word2[j - 1]不相同的时候，分三种情况：
  （1）删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
  （2）删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
  （3）同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
  最后取最小值，即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});
}
1
2
3
4
5

编辑距离
编辑距离给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数，两个字符串都可以增删改

• if (word1[i - 1] == word2[j - 1])
  不操作，即dp[i][j] = dp[i - 1][j - 1]

• if (word1[i - 1] != word2[j - 1])
  （1）增加：
  ①word1增加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-2为结尾的word1 与 i-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
  （2）删除：word2添加一个元素，相当于word1删除一个元素
  （3）替换：word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作， 即dp[i][j] = dp[i - 1][j - 1] + 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;
}
1
2
3
4
5
6