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

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

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

思路

  1. 动态规划，dp[i][j] 表示 t[:i] 作为 s[:j] 不同子序列的个数
  2. 想象 s 和 t 总是有一个相同的虚拟首字符，s[0][j] 均初始化为 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var numDistinct = function (s, t) {
  const dp = new Array(t.length + 1).fill(null).map(() => new Array(s.length + 1).fill(0))
  for (let j = 0; j <= s.length; ++j) {
    dp[0][j] = 1
  }
  for (let i = 0; i < t.length; ++i) {
    for (let j = 0; j < s.length; ++j) {
      if (t[i] !== s[j]) {
        dp[i + 1][j + 1] = dp[i + 1][j]
      } else {
        // 选用 s[i] 及不选用 s[i] 两种情况
        dp[i + 1][j + 1] = dp[i][j] + dp[i + 1][j]
      }
    }
  }
  return dp[t.length][s.length]
}