day-54 代码随想录算法训练营（19） 动态规划 part 15

392.判断子序列

思路一：双指针进行遍历判断

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()>t.size()) return false;
        int s_ptr=0,t_ptr=0;
        while(t_ptrsize()){
            if(s[s_ptr]==t[t_ptr]) s_ptr++;
            t_ptr++;
        }
        if(s_ptr==s.size()) return true;
        return false;
    }
};

思路二：动态规划

• 1.dp存储：以t[i-1]结尾，s[j-1]结尾的两个字符串最长子序列为dp[i][j]
• 2.动态转移方程：
•               if(t[i-1]==s[j-1]) dp[i][j]=dp[i-1][j-1]+1; 
•               else dp[i][j]=dp[i-1][j];
• 3.初始化：全为1
• 4.1~n

class Solution {
public:
    bool isSubsequence(string s, string t) {
 
        int n=t.size(),m=s.size();
        vectorint>>dp(n+1,vector<int>(m+1,0));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(t[i-1]==s[j-1]) dp[i][j]=dp[i-1][j-1]+1; 
                else dp[i][j]=dp[i-1][j];//看和s比较，t中的最长相同子序列
            }
        }
        return dp[n][m]==m ;
    }
};

115.不同的子序列

思路：

• 1.dp存储：以s[i-1]结尾的字符串可以组成以t[j-1]结尾的字符串 dp[i][j]个
• 2.动态转移方程：
•               if(s[i-1]==t[j-1]) 使用s[i-1] 和不使用 s[i-1]
•               else dp[i][j]=dp[i-1][j];
• 3.初始化：dp[i][0]一定为1，因为t不取；dp[0][j]一定为0，因为s不取；dp[0][0]为1
• 4.遍历顺序： 1~n

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

583.两个字符串的删除操作

思路：

• 1.dp存储：以word1[i-1]结尾，word2[j-1]结尾的两个字符串相同的最小操作数
• 2.动态转移方程：
•               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)
• 3.初始化：dp[i][0]=i   dp[0][j]=j
• 4.遍历顺序：1~n

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size(),m=word2.size();
        vectorint>>dp(n+1,vector<int>(m+1,0));
        for(int i=0;i<=n;i++) dp[i][0]=i;//word2长度为0时，word1需要全部删除
        for(int j=0;j<=m;j++) dp[0][j]=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-1][j]+1,dp[i][j-1]+1);//不等时，考虑哪边进行减少
            }
        }
        return dp[n][m];
    }
};