代码随想录算法训练营day54|第九章 动态规划part15

目录

392.判断子序列 

115.不同的子序列 

392.判断子序列 

bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=0;i<s.size();i++){
            for(int j=0;j<t.size();j++){
                if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
                else dp[i+1][j+1]=dp[i+1][j];
            }
        }
        if(dp[s.size()][t.size()]==s.size()) return true;
        else return false;
    }

dp[i][j]是以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。这里递推公式还是分成两个部分来推导——

• s[i] 与 t[j]相等。相等就说明可以利用当前的字符构成目标字符串，于是dp[i+1][j+1]的一部分就是dp[i][j]，换言之，这就是遍历到这个字符新增的方法数；但是除了用当前字符构成目标字符串，还可能不用当前的字符就可以构成目标字符串，相当于删除了当前字符所得到的方法数（dp[i+1][j]），换言之这部分就是遍历到这个字符之前累计的方法数。
• s[i] 与 t[j] 不相等。如果不相等，那就只能删除当前字符得到累计的方法数了。

 这道题的遍历顺序自然是从上到下，从左到右，故而必须初始化第一行列。dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数，那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数，那么dp[0][j]一定都是0，s如论如何也变成不了t。最后就要看一个特殊位置了，即：dp[0][0] 应该是多少，dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

最后狗测试点要求必须设置uint64_t这种类型的二维数组，这种比long long储存空间更大，也存储的是整型。

int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(t.size()+1,vector<uint64_t>(s.size()+1,0));
        for(int i=0;i<s.size();i++) dp[0][i]=1;
        for(int i=0;i<t.size();i++){
            for(int j=0;j<s.size();j++){
                if(t[i]==s[j]){
                    dp[i+1][j+1]=dp[i][j]+dp[i+1][j];
                }else{
                    dp[i+1][j+1]=dp[i+1][j];
                }
            }
        }
        return dp[t.size()][s.size()];
    }