題目描述:給定兩個字串 s 和 t,計算 s 的子序列中恰好等於 t 的數量(子序列是從原字串中刪去若干字元且不改變相對順序後所得的字串)。
解題思路:
二維動態規劃:
定義 dp[i][j] 為:在 s 的前 i 個字元中,t 的前 j 個字元作為子序列出現的次數。
初始化:
dp[i][0] = 1 對所有 i:空字串 t 是任何 s 前綴的子序列(正好一種,即選擇不取任何字元)dp[0][j] = 0 對所有 j > 0:空字串 s 不含任何非空的 t 作為子序列狀態轉移:
s[i-1] == t[j-1](當前字元匹配):
s[i-1] 來匹配 t[j-1]:貢獻 dp[i-1][j-1] 種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):由於每行只依賴上一行,可用滾動陣列將空間降至 O(n)。更新時從右往左遍歷,避免本行的值覆蓋上行需要的值。
範例:s = "rabbbit",t = "rabbit" → 答案為 3(有三個 b 可以選擇略過哪一個)
時間複雜度:O(m × n) — 其中 m = s.length(),n = t.length()。兩層迴圈各遍歷一次,每格計算 O(1)。
空間複雜度:O(n) — 使用一維滾動陣列,長度為 n + 1。若使用完整二維 DP 則為 O(m × n)。
1. If len(s) < len(t), return 0.
2. Initialize dp[0..n] = 0, dp[0] = 1.
3. For i from 1 to m:
a. For j from min(i, n) down to 1:
- If s[i-1] == t[j-1]:
dp[j] += dp[j-1]
- (else dp[j] stays the same — skip s[i-1])
4. Return dp[n].完整二維 DP O(m × n) 空間:建立 (m+1) × (n+1) 的 DP 表,初始化第一列 dp[i][0] = 1,然後按照轉移方程填表。邏輯清晰易懂,適合初學者理解,但記憶體使用為 O(m × n)。
遞迴 + 記憶化 O(m × n):定義 solve(i, j) 為從 s[i..] 中選出 t[j..] 的方案數,用二維陣列快取。若 s[i] == t[j],回傳 solve(i+1, j+1) + solve(i+1, j);否則只回傳 solve(i+1, j)。遞迴形式程式碼直覺,但可能有較大的函數呼叫開銷。
long long 是否足夠?t 中有多少個子序列等於 s(即 s 比 t 短),演算法是否可以直接對調?需要注意什麼?