代码随想录算法训练营day55|第九章 动态规划part16

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

代码随想录

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

这道题有两种动态规划的解法，一种是直接计算最小步数，另一种是通过计算最长公共子列长度来间接计算最小步数（=两个字符串字符总和 - 最长子列长度*2）。

如果直接考虑的话，分成了字符相等和字符不等的情况。如果字符相等的话，那就不加一；反之，如果字符不相等的话，就需要执行删除字符的操作，而删除字符的操作可以有三种情况：第1种情况是只删除word1字符串的字符，如果是这样的话，就相当于回退了word1的下标，然后因为执行了删除字符的操作，就在这个基础上再加1；第2种情况是只删除word2字符串的字符，这种情况同上；第3种情况是在两个字符串中都执行了删除字符的操作，这时候因为要删除两个字符，所以需要在这个的基础上加2，这种情况虽然可以被涵盖在前两种情况之中，也就是说同时删除两个字符，本来就是可以先删除一个再删除另一个的，只是同时删除两个的效率比较高。

这道题dp数组的初始化也比较讲究。由推导公式可知，当前值是从它上面的值和左边的值推导出来的，故而必须初始化第1行列，任意其中一个字符串为空的话，那么剩下的字符串的编辑距离就一定是它的字符串的长度，因为必须把它删除完了，才能使两个字符串相等。

int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {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][j - 1] + 1);}}}return dp[word1.size()][word2.size()];}

72. 编辑距离 

最终我们迎来了编辑距离这道题目，之前安排题目都是为了 编辑距离做铺垫。 

代码随想录

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

这道题的递推公式也比较复杂，首先还是考虑两个字符相等和不相等的情况。如果两个字符相等，那么编辑距离就不需要增加，直接等于两个指针回退一格的值；如果两个字符不相等，那么情况就比较复杂了，它可以执行插入、删除和替换三种操作，插入可以理解为让word2字符串回退一格再在此基础上加一（因为是插入的字符，所以word2这个字符就可以不做考虑了，就相当于word2回退了一格，而因为是插入在word1里面的，本来的字符不受影响，所以word1的指针不会回退一格），删除自然是在word1字符串上回退一格再在此基础上加一，而替换，因为在word1字符串和word2字符串里面都做了手脚，保证了这两个位置对应的字符一定是相等的，所以这两个位置的字符都不需要再做考虑了，孤儿两者都需要回退一格再在此基础上加一。

其他的诸如初始化还是遍历顺序都跟上一题是一样的，理由大同小异。

int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {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;}}}return dp[word1.size()][word2.size()];}

编辑距离总结篇 

做一个总结吧

代码随想录

判断子序列

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

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