LeetCode115：不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

代码如下：

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

dp含义：以i-1为结尾的s中有以j-1为结尾的t的个数为

dp递推公式：

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;
}

这个是因为先判断s[i - 1]==t[i - 1]的话，第一种情况就是我们的s和t串都往前走一个单位，这个算一个，然后再加上能够符合这个条件的方案，也即是dp[i - 1][j]，这个就是t串不走了，但是s串能往前走，并且还相等的。不相同的话，那么肯定是让dp[i - 1][j]也就是让s串往前走，不做任何操作。因为本题中说需要除以mod，那么我们需要在每一步都除以mod即可。
初始化：

这个我们需要画一个2*2的方格，也就是我们需要看见这个初始化是需要初始化成几？我们才能够往下面去进行后续递推公式的一个推到。这里就把dp[i][0] = 1;dp[0][j] = 0;

遍历顺序：

这个也需要我们去画一个2*2的方格，然后去看到这个dp[i][j]是从哪两个方向推导出来的，比如这个题，就可以从由上到下，由左到右推导出来这个公式，那么遍历顺序就直接从1开始就好

返回值：

这个题目需要返回的是这两个字符串的长度，因为我们就是根据这个字符串的长度来去求这个不同的子序列问题。