题目

给你两个字符串 s和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

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

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
++rabb++b++it++
++ra++b++bbit++
++rab++b++bit++

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
++ba++b**g**bag
++ba++bgba++g++
**b**abgb++ag++
ba**b**gb**ag**
babg++bag++

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

题解

public int numDistinct(String s, String t) {
    int sl = s.length(), tl = t.length();
    int[][] dp = new int[tl + 1][sl + 1];
    // t为空字符串 只有一种方法
    Arrays.fill(dp[0], 1);

    for (int i = 1; i <= tl; i++) {
        for (int j = 1; j <= sl; j++) {
            // 若都按照删除方法
            dp[i][j] = dp[i][j - 1];

            // 若字符一致
            if (s.charAt(j - 1) == t.charAt(i - 1)) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return dp[tl][sl];
}