你现在要解决的是 LeetCode 第 115 题「不同的子序列」（Distinct Subsequences），要求实现一个 numDistinct 方法，计算字符串 s 中有多少个不同的子序列恰好等于字符串 t。

问题理解与解题思路

首先明确「子序列」的定义：子序列是从原字符串中删除部分字符（可以不删）但不改变剩余字符相对顺序得到的新字符串。比如 s = "rabbbit"，t = "rabbit" 时，答案是 3，因为有 3 种方式从 s 中选出字符组成 t。

这道题的最优解法是动态规划（DP），核心思路是：

1. 定义 dp[i][j] 表示 s 的前 i 个字符中，能组成 t 的前 j 个字符的子序列数量。
2. 状态转移：
   • 如果 s[i-1] == t[j-1]（因为字符串索引从 0 开始，dp 索引从 1 开始），则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]：
     • dp[i-1][j-1]：用 s[i-1] 匹配 t[j-1]，剩余部分看 s 前 i-1 和 t 前 j-1 的结果；
     • dp[i-1][j]：不用 s[i-1] 匹配，剩余部分看 s 前 i-1 和 t 前 j 的结果。
   • 如果 s[i-1] != t[j-1]，则 dp[i][j] = dp[i-1][j]（只能不用 s[i-1]）。
3. 初始化：
   • dp[i][0] = 1：空字符串是任何字符串的子序列，所以 t 为空时，无论 s 多长，结果都是 1；
   • dp[0][j] = 0（j>0）：空字符串 s 无法组成非空的 t。

完整代码实现

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        // 边界条件：如果t的长度大于s，直接返回0（不可能组成）
        if (n > m) {
            return 0;
        }
        
        // 定义dp数组：dp[i][j] 表示s前i个字符中包含t前j个字符的子序列数量
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化：t为空时，所有s的前i个字符都有1种方式组成空字符串
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        
        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 情况1：当前字符相等，两种选择（用/不用s[i-1]）
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 情况2：当前字符不等，只能不用s[i-1]
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        // 最终结果：s的全部字符中包含t全部字符的子序列数量
        return dp[m][n];
    }

    // 测试用例
    public static void main(String[] args) {
        Solution solution = new Solution();
        // 测试用例1：s = "rabbbit", t = "rabbit" → 预期输出3
        System.out.println(solution.numDistinct("rabbbit", "rabbit")); // 输出3
        // 测试用例2：s = "babgbag", t = "bag" → 预期输出5
        System.out.println(solution.numDistinct("babgbag", "bag")); // 输出5
        // 测试用例3：s = "abc", t = "abcd" → 预期输出0
        System.out.println(solution.numDistinct("abc", "abcd")); // 输出0
    }
}

代码关键解释

1. 边界处理：先判断 t 的长度是否大于 s，如果是直接返回 0，避免无效计算。
2. DP数组初始化：dp[i][0] = 1 是核心初始化逻辑，对应「空字符串是任何字符串的子序列」。
3. 状态转移核心：
   • 字符相等时，累加「用当前字符」和「不用当前字符」的结果；
   • 字符不等时，仅继承「不用当前字符」的结果。
4. 测试用例：覆盖了常规场景、边界场景（t更长），验证代码正确性。

优化（空间复杂度）

上述代码的空间复杂度是 O(m*n)，可以优化为 O(n)（因为每次只依赖上一行的数据）：

public int numDistinctOpt(String s, String t) {
    int m = s.length();
    int n = t.length();
    if (n > m) return 0;
    
    // 用一维数组优化，仅保存上一行的结果
    int[] dp = new int[n + 1];
    dp[0] = 1; // 初始化：t为空时结果为1
    
    for (int i = 1; i <= m; i++) {
        // 从后往前遍历，避免覆盖还未使用的上一行数据
        for (int j = n; j >= 1; j--) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n];
}

优化思路：一维数组 dp[j] 等价于原二维数组的 dp[i][j]，从后往前遍历 j 可以避免更新 dp[j] 时覆盖 dp[j-1]（上一行的结果）。

总结

1. 核心思路：动态规划是解决该问题的最优解，通过 dp[i][j] 定义状态，利用字符是否相等推导状态转移方程。
2. 初始化关键：dp[i][0] = 1（空字符串是任何字符串的子序列），dp[0][j] = 0（j>0）。
3. 空间优化：一维DP数组可将空间复杂度从 O(m*n) 降至 O(n)，遍历方向需从后往前避免数据覆盖。

这个解法的时间复杂度是 O(m*n)（m、n 分别为 s、t 的长度），是该问题的最优时间复杂度。