题目
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
解答
- 动态规划
解题思路：
题目要求计算字符串 s 变换为字符串 t 的不同子序列数量。这类问题可以使用动态规划来解决。
我们使用 dp[i][j] 表示字符串 s 的前 i 个字符和字符串 t 的前 j 个字符之间的不同子序列数量。初始时，任何字符串变换为空字符串的方式都只有一种，即不选取任何字符，因此我们将 dp[i][0] 设置为 1。
然后，我们遍历字符串 s 和字符串 t 的所有字符组合，逐步计算 dp 数组。当 s[i-1] 和 t[j-1] 相等时，我们可以选择当前字符匹配或者不匹配。如果匹配，那么当前字符可以贡献 dp[i-1][j-1] 个子序列；如果不匹配，那么当前字符不会贡献新的子序列，继续使用 dp[i-1][j]。如果 s[i-1] 和 t[j-1] 不相等，那么当前字符不能匹配，只能选择不匹配，即使用 dp[i-1][j]。
最终，dp[m][n] 就是字符串 s 变换为字符串 t 的不同子序列数量，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length();
int n = t.length();
// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符之间的不同子序列数量
vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1, 0));
// 初始化：任何字符串变换为空字符串的方式都只有一种，即不选取任何字符
for (int i = 0; i <= m; ++i) {
dp[i][0] = 1;
}
// 状态转移
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// 如果 s[i-1] 和 t[j-1] 相等，则可以选择当前字符匹配或者不匹配
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// 如果不相等，则只能选择不匹配
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
};