115.不同的子序列

目标

给你两个字符串 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 <= 1000
• s 和 t 由英文字母组成

思路

有两个字符串 s 和 t，返回 s 的子序列中 t 的出现个数。

定义 dp[i][j] 表示 s[i, s.length - 1] 中 t[j, t.length - 1] 的子序列个数。dp[i][j] = (s[i] == t[j] ? dp[i + 1][j + 1] : 0) + dp[i + 1][j]。t 为空串时，初始化 dp[i][tl] = 1。

代码

/**
 * @date 2026-09-07 10:32
 */
public class NumDistinct115 {

    public int numDistinct(String s, String t) {
        int sl = s.length();
        int tl = t.length();
        char[] scs = s.toCharArray();
        char[] tcs = t.toCharArray();
        int[][] dp = new int[sl + 1][tl + 1];
        for (int i = 0; i <= sl; i++) {
            dp[i][tl] = 1;
        }
        for (int i = sl - 1; i >= 0; i--) {
            for (int j = tl - 1; j >= 0; j--) {
                dp[i][j] = (scs[i] == tcs[j] ? dp[i + 1][j + 1] : 0) + dp[i + 1][j];
            }
        }
        return dp[0][0];
    }

}

性能