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

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]+1
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[m][n];
    }
};

总结

编辑距离问题，初始化每个字符修改的次数。然后统计删除操作的个数

原文地址：https://blog.csdn.net/qq_48662659/article/details/140566625

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！