不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

  • 输入：s = “rabbbit”, t = “rabbit”

  • 输出：3
    解释：
    如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
    rabbbit
    rabbbit
    rabbbit

  • 输入：s = “babgbag”, t = “bag”

  • 输出：5
    解释：
    如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
    babgbag
    babgbag
    babgbag
    babgbag
    babgbag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var numDistinct = function(s, t) {
    let dp = Array.from({length: s.length + 1}, _ => Array(t.length + 1).fill(0));
    for (let i = 0; i <= s.length; i++) dp[i][0] = 1;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= t.length; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j -1]
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[s.length][t.length];
};