日期：2026年9月6日
LeetCode 題目連結：115. Distinct Subsequences
解題想法
困難題。題目給兩個字串 $s$、$t$，要計算 $s$ 的子字串之中有幾個等於 $t$，字串長度最長為 $1000$，要用動態規畫解題。
假設 $s$ 的長度為 $m$，$t$ 的長度為 $n$，開一個長度為 $(m+1) \times (n+1)$ 的二維陣列 $dp$，初始值先設為 0，$dp[i][0] = 1$，$dp[i][j]$ 代表檢查到 $s[i-1]$ 及 $t[j-1]$ 時，$s[0]$ 到 $s[i-1]$ 共有幾個子字串等於 $t[0:j]$。用兩層 for 迴圈更新 $dp$，外層跑 $i = 1$ 到 $i = m$，內層跑 $j = 1$ 到 $i = n$，如果 $s[i-1] == t[j-1]$，$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$；反之，$dp[i][j] = dp[i-1][j]$。由於更新時只需要用到前一次的狀態，可以用滾動陣列節省記憶體。由於答案很大，如果用 C 或 C++ 解題，$dp$ 的格式要用 unsigned long 才不會溢位。
Python 程式碼
二維陣列。Runtime: 419 ms, beats 49.82%. Memory: 75.56 MB, beats 56.33%.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
# 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
m, n = len(s), len(t)
dp = [[1] + [0]*n for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]
滾動陣列。Runtime: 213 ms, beats 85.86%. Memory: 19.53 MB, beats 82.38%.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
# 動態規畫，prev[j] 代表 s 之中等於 t[0:j] 的子字串數量
m, n = len(s), len(t)
prev = [1] + [0]*n # 前一個狀態，prev[0] = 1，空字串
for c in s: # 由 s 依序取出字母
curr = [1] + [0]*n # 現在的狀態 curr[0] = 1，空字串
for j in range(1, n+1): # 掃過 t 的每個字母
if t[j-1] == c: # 如果 t[j-1] 等於 c
curr[j] = prev[j-1] + prev[j] # 長度為前一個狀態索引值 j-1, j 相加
else: # 反之，繼承 prev[j]
curr[j] = prev[j]
prev, curr = curr, prev # 交換資料
return prev[-1] # 答案在 prev 最後一項
