第九章 动态规划 part15

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

双指针法：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int index=0;
        for(int i=0;i<t.size()&&index<s.size();i++){
            if(t[i]==s[index])  index++;
        }
        if(index==s.size())  return true;
        else  return false;
    }
};

动态规划法：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,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]+1;
                else  dp[i][j]=dp[i][j-1];
            }
        }
        if(dp[s.size()][t.size()]==s.size())  return true;
        else return false;
    }
};

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

写了上面那一道题再写一道思路就比较好想了。

主要是递推公式：

t[i-1]==s[j-1]时dp[i][j]由两种情况组成：

①不使用s[i-1]来匹配的匹配个数；

②使用s[i-1]匹配的个数；

t[i-1]！=s[j-1]时dp[i][j]由使用s[i-1]匹配的个数决定。

结合具体例子推导比较好理解。

初始化dp[0][j]=1:以i-1为结尾的s可以随便删除元素，出现空字符串的个数。

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<int>> dp(t.size()+1,vector<int>(s.size()+1,0));
        int mod=(int)1e9+7;
        for(int j=0;j<=s.size();j++)  dp[0][j]=1;
        for(int i=1;i<=t.size();i++){
            for(int j=1;j<=s.size();j++){
                if(t[i-1]==s[j-1])  dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%mod;
                else  dp[i][j]=dp[i][j-1];
            }
        }
        return (dp[t.size()][s.size()])%mod;
    }
};