当前位置：首页 > news >正文

【c++刷题笔记-动态规划】day45： 115.不同的子序列、583. 两个字符串的删除操作、 72. 编辑距离

news 来源：原创 2024/9/20 11:43:21

115. 不同的子序列 - 力扣（LeetCode）

思路：用s与t比较相等就判断dp[i-1][j-1]+dp[i-1][j]两个方向的值，不相同就判断dp[i-1][j]方向

重点：if(s[i-1]==t[j-1]){
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
}else{
dp[i][j]=dp[i-1][j]%mod;
}

class Solution {
public:const int mod=1e9+7;int numDistinct(string s, string t) {int n=s.size(),m=t.size();vector<vector<long>>dp(n+1,vector<long>(m+1,0));for(int i=0;i<n;i++){dp[i][0]=1;//当t为零时为s的一个子序列}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i-1]==t[j-1]){//用s比较因为s可能有重复的字符，所以从dp[i-1][j-1]+dp[i-1][j]两个方向推导dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;}else{//相当于在s中删除字符dp[i][j]=dp[i-1][j]%mod;}}}return dp[n][m];}
};

583. 两个字符串的删除操作 - 力扣（LeetCode）

思路：相同就延续之前的状态，不想同每次删除word1和word2都需要一次操作。

class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size(),m=word2.size(),ans=INT_MIN;vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(int i=0;i<=n;i++){dp[i][0]=i;//word2为0，每个字符需要修改i次}for(int j=0;j<=m;j++){dp[0][j]=j;//word1为0，每个字符需要修改j次}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1];///相同不需要修改}else{dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1);//删除一个字符然后次数加一}}}return dp[n][m];}
};

72. 编辑距离 - 力扣（LeetCode）

思路：相同就延续之前的状态，不想同每次删除word1和word2都需要一次操作。删除操作隐含了同时删除两个dp[i-1][j-1]+2。增加和删除操作数是一样的。替换操作就是在原来的基础是加一就相同了

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(),n=word2.size();vector<vector<int>>dp(m+1,vector<int>(n+1));for(int i=0;i<=m;i++){dp[i][0]=i;//word2为0，每个字符需要修改i次}for(int j=0;j<=n;j++){dp[0][j]=j;//word1为0，每个字符需要修改j次}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1[i-1]==word2[j-1]){//相同不修改dp[i][j]=dp[i-1][j-1];}else{//删除和增加操作数是一样的，替换操作是dp[i-1][j-1]+1dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;}}}return dp[m][n];}
};