题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
ba b g bag
ba bgba g
b abgb ag
ba b gb ag
babg bag

提示：

• 0 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

  解题方法

  动态规划

  设定动态数组dp[i][j]表示在s下标范围0~i-1范围内，能够得到子序列为t中0~j-1的个数。如下图所示，对于dp[i][0]，由于任何序列都包含空序列，所以dp[i][0]=1；对于dp[0][j] (j>0)，因为任何字符不为空，所以dp[0][j]=0 (j>0)。其递推关系如下所示：
  
  具体如下图所示，s[i-1]=t[j-1]相等时由两部分组成：① 在s[0, i-2]中匹配t[0. j-2]，个数为dp[i-1][j-1]；② 在s[0, i-2]中匹配t[0, j-1]，个数为dp[i-1][j]。
  
  时间复杂度O(mn)，空间复杂度O(min(m, n))
  C++代码：

  class Solution {
  public:
    int numDistinct(string s, string t) {
        int n1 = s.size();
        int n2 = t.size();
        vector<long long> dp(n2+1, 0);
        dp[0] = 1;
        for(int i=1; i<=n1; i++) {
            for(int j=1, pre = dp[0]; j<=n2; j++) {
                int cur = dp[j];
                if(s[i-1]==t[j-1])  dp[j] += pre;   
                pre = cur;
            }
        }
        return dp[n2];
    }
  };