不同的子序列

由于今天的每日一题比较简单，刷一下三叶姐这边的每日一题。

题目链接 (opens new window)

难度：中等

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

示例 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 <= 1000
s 和 t 由英文字母组成

dp好难！看了三叶姐和官方解法，才大概理解本题的解法。

此外这种字符串匹配问题一般也有通用的dp状态方程，也有一些小技巧。

1. 状态方程：dp[i][j]表示s的前i个字符和t的前j个字符的匹配（不同题目匹配条件不一致，在本题为子序列）个数。
2. 本题小技巧：在s和t的前面都插入一个空字符，方便递推累加，由此可得到dp[i][0]固定为1，因为空字符串是任何字符串的子序列。

function numDistinct(s: string, t: string): number {
    const n = s.length, m = t.length
    const dp = new Array(n+1).fill(0).map(() => new Array(m+1).fill(0))
    for(let i = 0; i <= n; i++) {
        dp[i][0] = 1
    }
    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= m; j++) {
            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[n][m]
};

时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。

点了下提交记录发现这题我在两年前就做过了--。而且当时用的是递归+记忆化搜索的方式，感觉也挺好理解的，相当于搞了俩个指针在s和t上面，如果是t的指针先到最后，说明在s中找到了一种子序列等于t的情况了。

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
  const slen = s.length, tlen = t.length
  const memo = new Array(slen).fill(0).map(() => new Array(tlen).fill(-1))
  function dfs(i, j) {
    // 这个必须在前， 如果当两者都走到了最后，优先判断j， 避免漏了
    if (j >= tlen) {
      return 1
    }
    if (i >= slen) {
      return 0
    }
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }
    if (s[i] == t[j]) {
      // 可以理解为 要不要计算当前字符 所以有两种情况
      memo[i][j] = dfs(i + 1, j + 1) + dfs(i + 1, j)
    }
    else {
      memo[i][j] = dfs(i + 1, j)
    }
    return memo[i][j]
  }
  return dfs(0, 0)
};