数据结构与算法｜算法总结｜动态规划之编辑距离总结篇(或者叫两个序列之间的比较问题)_动态规划 编辑距离

啥也不说先上图！

本节一共总结了六道题，个人认为作为二维dp的典型用法，所以归纳到了一起，方便对比、类比学习。

718.最长重复子序列

力扣题目链接
文章链接
两个整数数组A、B，返回两个数组中 公共的、长度最长的子数组的长度。

从题目我们可以看出，本题将来和后面最大的不一样就是要求公共的子数组。其实就是要求中间是不能断开的。所以这就决定了我们遇到当前元素不想等时，我们直接不管，然后就是需要一个result来实时存储当前的最大公共子数组的长度。

dp[i][j] ：以下标i - 1为结尾的num1，和以下标j - 1为结尾的num2，最长重复子数组长度为dp[i][j]。
为什么要定义成i-1结尾和以j-1结尾呢？就是为了让初始化比较方便，在后续的子序列的二维dp中，都是采用这样的形式

递推公式：
dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。

• if (nums[i - 1] == nums2[j - 1])
  • 让最长重复子数组+1
  • 用result保存当前结果
• if(nums[i - 1] != nums2[j - 1])
  • 直接不管！

即当nums[i - 1] 和nums2[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1

根据递推公式可以看出，遍历i 和 j 要从1开始！

if (nums1[i - 1] == nums2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
1
2

1143.最长公共子序列

力扣题目链接
文章链接
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
本题跟上面那道【718.最长重复子序列】只不过是不要求是连续起来的。
既然不要求连续，我们这里可以想象我们需要做删除操作（编辑距离思路）

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

• $if(test[i-1]==text2[j-1])$
  • 我们还是记录最长公共子序列 + 1
• $if(test[i-1]!=text2[j-1]$
  • 当前的不匹配？那就只能考虑text1的前一个或者考虑text2的前一个了，取一个最大的！
  • 不同时，说明当前字符不能同时出现在最长公共子序列中，因此最长公共子序列的长度取决于去掉text1的最后一个字符和去掉text2的最后一个字符后的两个子问题，即 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。
  • 本质上就是把之前可能相等的信息继承过来

状态转移公式：

if (test[i - 1] == text2[j - 1] {
	dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
1
2
3
4
5

45.不相交的线

真正做到了跟1143最长公共子序列一模一样
力扣题目链接
文章链接

392.判断子序列

力扣题目链接
文章链接
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

本题其实最合适的算法是双指针和贪心。但是它太适合用来做编辑距离的开篇了。

这里重点讲解它的dp数组和递推公式的推导：

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。如果我们到时候记录到

这里为什么要定义成下标i-1为结尾和以下标j-1为结尾呢？因为如果以i、j结尾，会让初始化的写法非常麻烦

递推公式：

1. if (s[i - 1] == t[j - 1])
   • t中找到了一个字符在s中也出现了，相同子序列长度+1
2. if (s[i - 1] != t[j - 1])
   • 相当于t要删除元素，继续匹配。那就直接继承t的前一个元素信息喽

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

115.不同的子序列

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

这里我们当然要把dp数组定义成个数
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]也就是说子序列出现的个数可以有两部分组成。

• 用s[i - 1]来匹配 ，个数为dp[i - 1][j - 1]
• 不用s[i - 1]来匹配，个数为dp[i - 1][j]
  所以说这里千万不要有什么+1 -1的操作，我们的是否用s[i-1]来匹配就已经包含了出现个数的操作

如果不想等的话，dp[i][j]只有一个部分组成，不用s[i - 1]来匹配，也就是dp[i][j]=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

583.两个字符的删除操作

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

现在已经是编辑距离直接不装了，明示删除操作使得word1和word2相同。

dp设定的思路还是不变：
dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

如果相同：直接dp[i][j]=dp[i-1][j-1]表示不用删除
如果不同：

• 删word1[i - 1]，操作数就是dp[i-1][j] + 1
• 删word2[j - 1]，操作数是dp[i][j-1] + 1
• 删word1[i - 1]和word2[j - 1]，操作数就是dp[i-1][j-1] + 2。

这里有一个小trick:
dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2。因为其实dp[i][j-1]已经不靠里word2的j-1个字符了，在此基础上，如果再删除woed1的第 i -1个字符，实际就相当于达到了同时删除两个字符的效果，也就是操作数+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});
    //dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
1
2
3
4
5
6

72.编辑距离

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

已经是一摸一样了，就是操作变多了。

编辑距离我们可以增、删、换

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换
1
2
3
4
5
6

1. 不操作
   两个对应元素相等的时候直接不操作，继承前面的
   dp[i][j] = dp[i - 1][j - 1]

2. 增

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;

3. 删
word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！

所以我们直接合并到“增”的分支

4. 换

替换元素，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;
}
1
2
3
4
5
6