【代码随想录算法训练Day51】LeetCode 115.不同的子序列、LeetCode 583. 两个字符串的删除操作、LeetCode 72. 编辑距离

Day51 动态规划第十二天

LeetCode 115.不同的子序列

dp数组的含义：以i-1为结尾的s中有以j-1为结尾的t的个数为dp[i][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]
初始化：dp[i][0]=1 dp[0][j]=0 dp[0][0]=1
遍历顺序：从左到右从上到下

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));
        for(int i=0;i<s.size();i++) dp[i][0]=1;
        for(int j=1;j<t.size();j++) dp[0][j]=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];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};

dp数组的含义：以i-1和j-1结尾的两个数组相同需要的最小操作次数为dp[i][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,dp[i-1][j-1]+2)
初始化：dp[0][j]=j dp[i][0]=i 其余为0
遍历顺序：从左到右从上到下

class Solution {
public:
    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()];
    }
};

LeetCode 72. 编辑距离

dp数组的含义：以i-1和j-1为结尾的两个字符串相同的最少操作次数
递推公式：if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]
else 增、删 dp[i][j]=dp[i-1][j]+1 dp[i][j-1]+1
替换 dp[i][j]=dp[i-1][j-1]+1
初始化：dp[i][0]=i dp[0][j]=j
遍历顺序：从左到右从上到下

class Solution {
public:
    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()];
    }
};