代码随想录训练营Day51

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

今天是跟着代码随想录刷题的第51天，主要学习了不同的子序列、两个字符串的删除操作、编辑距离

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、不同的子序列

思路：
这道题的dp[i][j]是[0,i-1]的s最多能有多少种方式组合成[0,j-1],初始化dp[0][i]空字符串组成不了，所以是0，dp[i][0]是字符串中找多少个方式是空字符串，那就是全部删除掉就可以了，所以只有这一种，至于dp[0][0]空字符串本身就是空字符串不用删减所以也是一种，递推公式如果s[i-1]==t[j-1]，则dp[i][j]=dp[i-1][j-1]+dp[i-1][j]中， dp[i-1][j-1]是最后一个i来的时候，一共多了多少种组合，dp[i-1][j]是上一个有多少种组合，所以合理，如果最后一个元素不相等，就说明加不加最后一个元素没区别，直接等于dp[i-1][j]
代码：

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));for(int i=0;i<=s.size();i++) dp[i][0]=1;for(int i=1;i<=t.size();i++) dp[0][i]=0;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//dp[i-1][j-1]是最后一个i来的时候，一共多了多少种组合，dp[i-1][j]是上一个有多少种组合}else{dp[i][j]=dp[i-1][j];}}}return dp[s.size()][t.size()];}
};

二、两个字符串的删除操作

思路：
关键是dp数组的定义，dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数，这里i-1和j-1是因为初始化比较简单，递推公式推导见文中的注释
代码：

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size()+1,vector<uint64_t>(word2.size()+1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i=0;i<=word1.size();i++)//初始化{dp[i][0]=i;}for(int i=0;i<=word2.size();i++)//初始化{dp[0][i]=i;}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);//如果最后两个不一样，就看到底是哪个变动需要的步数，变动的那个把那行给去掉一个加上去掉需要的步数1}}}return dp[word1.size()][word2.size()];}
};

三、编辑距离

思路：
如果最后两个不一样，可能是增加删减或者替换，先讲一下删除元素，删除元素就是，我要删除的那个元素不管，上面缺一个元素i-1和下面j先操作，操作完以后，把上面那个元素删除就好了，增加和删减其实一样，因为我增加去迎合你，是不是就相当于你减去一个迎合我的操作是一样的，如果是替换，那么我结尾的元素都不用管了，把i-1,j-1的元素操作完成，然后最后一对两个元素换成一样的一步骤就可以，所以是dp[i-1][j-1]+1

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size()+1,vector<uint64_t>(word2.size()+1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i=0;i<=word1.size();i++)//初始化{dp[i][0]=i;}for(int i=0;i<=word2.size();i++)//初始化{dp[0][i]=i;}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(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);//如果最后两个不一样，可能是增加删减或者替换}}}return dp[word1.size()][word2.size()];}
};