LeetCode 115：不同的子序列

LeetCode 115：不同的子序列

问题本质与核心挑战

给定两个字符串 s 和 t，需计算 s 的子序列中 t 出现的个数。子序列的定义是：通过删除 s 中的某些字符（可删除0个），保持字符相对顺序不变得到的序列。

核心挑战：

• 直接枚举所有子序列会导致 组合爆炸（时间复杂度指数级）；
• 需通过 动态规划 高效推导状态转移，避免重复计算。

核心思路：二维动态规划

1. 状态定义

设 dp[i][j] 表示：

• s 的前 i 个字符（s[0..i-1]）；
• t 的前 j 个字符（t[0..j-1]）；
  的匹配方案数（即 s 的前 i 个字符中，子序列等于 t 的前 j 个字符的个数）。

2. 状态转移方程

分两种情况：

• 情况 1：s[i-1] == t[j-1]（当前字符匹配）：

  • 用 s[i-1] 匹配 t[j-1]：方案数继承自 dp[i-1][j-1]（前面的子序列已匹配，当前字符参与匹配）；
  • 不用 s[i-1] 匹配 t[j-1]：方案数继承自 dp[i-1][j]（前面的子序列已匹配，当前字符不参与）。
    因此：

  dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
  

• 情况 2：s[i-1] != t[j-1]（当前字符不匹配）：
  只能忽略 s[i-1]，方案数继承自 dp[i-1][j]（前面的子序列已匹配，当前字符不参与）。
  因此：

  dp[i][j] = dp[i-1][j];
  

3. 初始化逻辑

• 空字符串匹配：dp[0][0] = 1（空字符串是自身的子序列）。
• s 非空，t 为空：任何 s 的子序列都包含空字符串，故 dp[i][0] = 1（i ≥ 0）。
• s 为空，t 非空：无法匹配，故 dp[0][j] = 0（j > 0）。

算法步骤详解（以示例 1 为例：s = "rabbbit", t = "rabbit"）

步骤 1：初始化 DP 表

• n = 7（s 长度），m = 6（t 长度）。
• DP 表维度 8×7（i 从 0 到 7，j 从 0 到 6）。
• 初始化：
  • dp[0][0] = 1；
  • 第一列（j=0）：dp[i][0] = 1（i=0~7）；
  • 第一行（i=0，j>0）：dp[0][j] = 0（j=1~6）。

步骤 2：逐行填充 DP 表

遍历 i（1~7）和 j（1~6），根据字符是否匹配应用转移方程：

完整代码（Java）

class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length();
        int m = t.length();
        // 若t比s长，直接返回0（不可能匹配）
        if (m > n) return 0;
        
        // dp[i][j]：s前i个字符与t前j个字符的匹配方案数
        int[][] dp = new int[n + 1][m + 1];
        
        // 初始化：空字符串匹配空字符串
        dp[0][0] = 1;
        // s的前i个字符匹配空字符串（只有空序列一种可能）
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
        }
        // 空s匹配非空t（不可能，方案数为0）
        for (int j = 1; j <= m; j++) {
            dp[0][j] = 0;
        }
        
        // 填充DP表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(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];
    }
}

代码逐行解释

1. 边界处理：若 t 长度大于 s，直接返回 0（无法匹配）。
2. DP 表初始化：
   • dp[0][0] = 1：空字符串互相匹配。
   • 第一列（j=0）：任何 s 的前缀都包含空序列，故全为 1。
   • 第一行（i=0，j>0）：空 s 无法匹配非空 t，故全为 0。
3. 状态转移：
   • 遍历 s 和 t 的每个前缀，根据字符是否匹配，选择累加两种情况或继承前一状态。
4. 结果返回：dp[n][m] 表示 s 全串与 t 全串的匹配方案数。

复杂度分析

• 时间复杂度：O(n×m)（双重遍历，n 是 s 长度，m 是 t 长度）。
• 空间复杂度：O(n×m)（存储 DP 表）。

优化思路：若需降低空间复杂度，可使用滚动数组将空间优化为 O(m)（仅保留前一行状态），但会牺牲部分可读性。

该方法通过 动态规划清晰建模状态转移，将指数级复杂度的问题降为多项式级，是字符串匹配类问题的经典解法。核心在于理解“匹配时的两种选择（用或不用当前字符）”，并通过 DP 表高效记录中间结果。