动态规划之编辑距离总结篇

╰+攻爆jí腚メ 2023-10-16 18:00 13阅读 0赞

#### 动态规划之编辑距离总结篇 ####

*  1. 判断子序列
 *  2. 不同的子序列
 *  3. 两个字符串的删除操作
 *  4. 编辑距离

## 1. 判断子序列 ##

**动态规划：392.判断子序列**给定字符串 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];

## 2. 不同的子序列 ##

**动态规划：115.不同的子序列** 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

本题虽然也只有删除操作，不用考虑替换增加之类的，但相对于**动态规划：392.判断子序列** 就有难度了，这道题目双指针法可就做不了。

当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[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];
    }

## 3. 两个字符串的删除操作 ##

**动态规划：583.两个字符串的删除操作**给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。

本题和**动态规划：115.不同的子序列**相比，其实就是两个字符串可以都可以删除了，情况虽说复杂一些，但整体思路是不变的。

*  当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\});

状态转移方程：

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});
    }

## 4. 编辑距离 ##

**动态规划：72.编辑距离**给你两个单词 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 与 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替换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;

**参考资料**：[代码随想录-动态规划之编辑距离总结篇][-]

[-]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97