mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
197 lines
8.0 KiB
Markdown
Executable File
197 lines
8.0 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
# 动态规划之编辑距离总结篇
|
||
|
||
本周我们讲了动态规划之终极绝杀：编辑距离，为什么叫做终极绝杀呢？
|
||
|
||
细心的录友应该知道，我们在前三篇动态规划的文章就一直为 编辑距离 这道题目做铺垫。
|
||
|
||
## 判断子序列
|
||
|
||
[动态规划：392.判断子序列](https://programmercarl.com/0392.判断子序列.html) 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
|
||
|
||
|
||
这道题目 其实是可以用双指针或者贪心的的，但是我在开篇的时候就说了这是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。
|
||
|
||
* if (s[i - 1] == t[j - 1])
|
||
* t中找到了一个字符在s中也出现了
|
||
* if (s[i - 1] != t[j - 1])
|
||
* 相当于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];
|
||
```
|
||
|
||
## 不同的子序列
|
||
|
||
[动态规划：115.不同的子序列](https://programmercarl.com/0115.不同的子序列.html) 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
|
||
|
||
本题虽然也只有删除操作，不用考虑替换增加之类的，但相对于[动态规划：392.判断子序列](https://programmercarl.com/0392.判断子序列.html)就有难度了，这道题目双指针法可就做不了。
|
||
|
||
|
||
当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[i - 1]来匹配，都相同了指定要匹配啊。
|
||
|
||
例如： 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];
|
||
|
||
|
||
状态转移方程：
|
||
```CPP
|
||
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];
|
||
}
|
||
```
|
||
|
||
## 两个字符串的删除操作
|
||
|
||
[动态规划：583.两个字符串的删除操作](https://programmercarl.com/0583.两个字符串的删除操作.html)给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。
|
||
|
||
本题和[动态规划：115.不同的子序列](https://programmercarl.com/0115.不同的子序列.html)相比，其实就是两个字符串可以都可以删除了，情况虽说复杂一些，但整体思路是不变的。
|
||
|
||
|
||
* 当word1[i - 1] 与 word2[j - 1]相同的时候
|
||
* 当word1[i - 1] 与 word2[j - 1]不相同的时候
|
||
|
||
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
|
||
|
||
当word1[i - 1] 与 word2[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
|
||
|
||
那最后当然是取最小值，所以当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});
|
||
|
||
状态转移方程：
|
||
```CPP
|
||
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});
|
||
}
|
||
```
|
||
|
||
|
||
## 编辑距离
|
||
|
||
[动态规划：72.编辑距离](https://programmercarl.com/0072.编辑距离.html) 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
|
||
|
||
|
||
编辑距离终于来了，**有了前面三道题目的铺垫，应该有思路了**，本题是两个字符串可以增删改，比 [动态规划：判断子序列](https://programmercarl.com/0392.判断子序列.html)，[动态规划：不同的子序列](https://programmercarl.com/0115.不同的子序列.html)，[动态规划：两个字符串的删除操作](https://programmercarl.com/0583.两个字符串的删除操作.html)都要复杂的多。
|
||
|
||
|
||
在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：
|
||
|
||
* 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];
|
||
|
||
此时可能有同学有点不明白，为啥要即dp[i][j] = dp[i - 1][j - 1]呢？
|
||
|
||
那么就在回顾上面讲过的dp[i][j]的定义，word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。
|
||
|
||
在下面的讲解中，如果哪里看不懂，就回想一下dp[i][j]的定义，就明白了。
|
||
|
||
**在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！**
|
||
|
||
if (word1[i - 1] != word2[j - 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;
|
||
|
||
这里有同学发现了，怎么都是添加元素，删除元素去哪了。
|
||
|
||
**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;
|
||
|
||
递归公式代码如下：
|
||
|
||
```CPP
|
||
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;
|
||
}
|
||
```
|
||
|
||
## 总结
|
||
|
||
心思的录友应该会发现我用了三道题做铺垫，才最后引出了[动态规划：72.编辑距离](https://programmercarl.com/0072.编辑距离.html) ，Carl的良苦用心呀，你们体会到了嘛！
|
||
|
||
## 其他语言版本
|
||
|
||
### Java：
|
||
|
||
```java
|
||
class Solution {
|
||
public int minDistance(String word1, String word2) {
|
||
int m = word1.length();
|
||
int n = word2.length();
|
||
int[][] dp = new int[m+1][n+1];
|
||
for(int i = 1; i <= m; i++){
|
||
dp[i][0] = i;
|
||
}
|
||
for(int i = 1; i <= n; i++){
|
||
dp[0][i] = i;
|
||
}
|
||
for(int i = 1; i <= m; i++){
|
||
for(int j = 1; j <= n; j++){
|
||
int left = dp[i][j-1]+1;
|
||
int mid = dp[i-1][j-1];
|
||
int right = dp[i-1][j]+1;
|
||
if(word1.charAt(i-1) != word2.charAt(j-1)){
|
||
mid ++;
|
||
}
|
||
dp[i][j] = Math.min(left,Math.min(mid,right));
|
||
}
|
||
}
|
||
return dp[m][n];
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|