给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
示例 1：
输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
示例 2：
输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
提示：
1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
动态规划
class Solution {
public:
int numDistinct(string s, string t) {
int MOD = 1e9 + 7;
int m = s.size(), n = t.size();
if(n > m){
return 0;
}
vector<vector<int>> f(m+1, vector<int>(n+1));
for(int i = 0; i <= m; i++){
f[i][0] = 1;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= min(i, n) ; j++){
if(s[i-1] == t[j-1]){
f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;
}
else{
f[i][j] = f[i-1][j] % MOD;
}
}
}
return f[m][n];
}
};
时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。
空间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。创建了 m+1 行 n+1 列的二维数组 dp。
这个题运用了动态规划的思想，我们首先定义一个二维动态数组f[i][j]，设 f[i][j] 表示字符串 s 的前 i 个字符中，子序列中 t 的前 j 个字符出现的次数。
如果 s[i - 1] == t[j - 1]，那么 f[i][j] 既可以选择使用 s[i - 1] 来匹配 t[j - 1]，也可以不使用 s[i - 1]。此时状态转移方程为：
f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;
如果 s[i - 1] != t[j - 1]，则无法匹配 t[j - 1]，因此只能继承之前的状态：
f[i][j] = f[i - 1][j]
最后返回f[m][n]。
优化：滚动数组
class Solution {
public:
int numDistinct(string s, string t) {
int MOD = 1e9 + 7;
int m = s.size(), n = t.size();
if(n > m){
return 0;
}
vector<int> f(n+1);
f[0] = 1;
for(int i = 1; i <= m; i++){
for(int j = min(i, n); j >= 1 ; j--){
if(s[i-1] == t[j-1]){
f[j] = (f[j-1] + f[j]) % MOD;
}
}
}
return f[n];
}
};
我们可以观察到f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;中，f[I][j]上一行的前一个字符转换而来，还有由同一行的前一个字符转换而来。所以我们可以省去行的空间，只定义一个包含列的一维数组f[n]，我们在循环中让j倒序，我们就有f[j-1]等同于f[i-1][j-1]，f[j]等同于f[i-1][j]。并且在f[i][j] = f[i-1][j] % MOD;中，f[i-1][j]会转换成f[j] = f[j]，所以我们不需要列出这种情况。
