LeetCode Distinct Subsequences：動態規劃計算不同子序列數

題目描述

給定字符串 S 和 T，計算 S 中有多少個不同的子序列等於 T。子序列保持相對順序刪除部分字符得到。

範例：S="rabbbit", T="rabbit" → 輸出 3。

解法分析

遞歸/備忘錄（超時風險）

逐字符匹配，相同則遞歸處理剩餘子串。存在大量重疊子問題，需備忘錄優化。

動態規劃（標準解）

定義 dp[i][j]：T[i:] 在 S[j:] 中作為子序列出現的次數。

• 若 T[i] == S[j]：dp[i][j] = dp[i][j+1] + dp[i+1][j+1]（不匹配當前字符 + 匹配當前字符）。
• 否則：dp[i][j] = dp[i][j+1]。

邊界：dp[|T|][*] = 1（空串是任意串的子序列），dp[*][|S|] = 0（非空串不匹配空串）。

自底向上填表，答案為 dp[0][0]。時間 O(|S|×|T|)，空間可優化至 O(|S|)。

參考代碼 (Java)

public class Solution {
    public int numDistinct(String S, String T) {
        if (T.isEmpty() || S.length() < T.length()) return 0;
        int m = T.length(), n = S.length();
        int[][] dp = new int[m + 1][n + 1];
        Arrays.fill(dp[m], 1); // 空 T
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n + i - m; j >= 0; --j) { // 優化：j 至少剩餘足夠字符
                if (S.charAt(j) == T.charAt(i))
                    dp[i][j] = dp[i][j+1] + dp[i+1][j+1];
                else
                    dp[i][j] = dp[i][j+1];
            }
        }
        return dp[0][0];
    }
}

空間優化版 (1D DP)

public int numDistinct(String S, String T) {
    int[] dp = new int[S.length() + 1];
    Arrays.fill(dp, 1); // dp[j] 表示空 T 在 S[j:] 中出現 1 次
    for (int i = T.length() - 1; i >= 0; --i) {
        int prev = 0; // 對應 dp[i+1][j+1]
        for (int j = S.length() - 1; j >= 0; --j) {
            int temp = dp[j];
            if (S.charAt(j) == T.charAt(i))
                dp[j] = dp[j+1] + prev;
            else
                dp[j] = dp[j+1];
            prev = temp;
        }
    }
    return dp[0];
}