LeetCode 115 詳解：Distinct Subsequences (不同子序列計數)

題目描述

給定字串 S 和 T，計算 T 作為 S 子序列出現的次數。子序列定義：從 S 刪除若干字符（可不刪除），剩餘字符順序不變形成 T。

範例：S = "rabbbit", T = "rabbit" → 輸出 3。
三種對應：rabbbit, rabbbit, rabbbit（粗體為刪除的 'b'）。

動態規劃解法

狀態定義

dp[i][j]：S[0..i-1] 前 i 字符中，包含 T[0..j-1] 作為子序列的次數。

轉移方程

• 若 S[i-1] == T[j-1]：兩種選擇
  1. 匹配這對字符 → dp[i-1][j-1]
  2. 不匹配，忽略 S[i-1] → dp[i-1][j]
  dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
• 若 S[i-1] != T[j-1]：只能忽略 S[i-1] dp[i][j] = dp[i-1][j]

邊界條件

• dp[i][0] = 1：空串是任意串的子序列（1 種方式）
• dp[0][j>0] = 0：空串不包含非空子序列

空間優化：一維 DP

觀察轉移只依賴 i-1 行，可壓縮為一維陣列 dp[j] 表示當前行。關鍵：j 必須從大到小遍歷，否則會覆蓋 dp[j-1]（即上一行的 dp[j-1]）。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(m):
            # 逆序遍歷 j，保證用到的是上一輪的 dp[j-1]
            for j in range(n - 1, -1, -1):
                if t[j] == s[i]:
                    dp[j + 1] += dp[j]
        return dp[n]

執行過程圖解

S = "rabbbit", T = "rabbit"

最終 dp[6] = 3，與預期一致。

複雜度分析

• 時間：O(m × n) — 雙重循環
• 空間：O(n) — 一維 DP 陣列

關鍵點總結

1. 子序列 vs 子串：子序列不要求連續，DP 狀態體現「選或不選」決策
2. 逆序遍歷 j：一維 DP 壓縮的核心技巧，避免狀態覆蓋
3. 大數處理：LeetCode 測試用例結果可能超 32 位，Python 無憂慮，C++ 需用 unsigned long long 或 uint64_t
4. 優化：若字符集較小，可預處理 S 中各字符位置列表，跳過不匹配字符

總結

Distinct Subsequences 是二維 DP 压缩為一維的經典範例。核心在於：「當字符匹配時，方案數 = 使用該匹配的方案數 + 不使用該匹配的方案數」。逆序遍歷保證狀態正確性，是掌握 DP 空間優化的關鍵技巧。