給定字串
s和t，回傳s的子序列中等於t的個數。子序列是從原字串中刪除若干字元（可以不刪）後得到的序列。
Example:
Input: s = “rabbbit”, t = “rabbit” Output: 3
Intuition
TIP
dp[i][j] 代表 s[0..i-1] 的子序列中等於 t[0..j-1] 的個數：匹配就加上「不用 s[i-1]」和「用 s[i-1]」兩種，不匹配就只能跳過。
- 若
s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]dp[i-1][j-1]：用 s[i-1] 匹配 t[j-1]dp[i-1][j]：不用 s[i-1]
- 若不同：
dp[i][j] = dp[i-1][j]（只能跳過 s[i-1]） - 基底：
dp[i][0] = 1（空字串 t 有一種匹配方式）
Approaches
1. 2D DP Table — O(m * n) / O(m * n)
- Idea: 建立
(m+1) x (n+1)的表格，其中 m = s.length, n = t.length。 - Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun numDistinct(s: String, t: String): Int {
val m = s.length
val n = t.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 0..m) dp[i][0] = 1
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = dp[i - 1][j]
if (s[i - 1] == t[j - 1]) {
dp[i][j] += dp[i - 1][j - 1]
}
}
}
return dp[m][n]
}
}⭐ 2. 1D DP (Space Optimized) — O(m * n) / O(n)
- Idea: 用一維陣列從右到左更新（因為依賴
dp[j-1]的舊值，必須逆向遍歷）。 - Time:
O(m * n) - Space:
O(n)
class Solution {
fun numDistinct(s: String, t: String): Int {
val n = t.length
val dp = IntArray(n + 1)
dp[0] = 1
for (i in 1..s.length) {
for (j in n downTo 1) {
if (s[i - 1] == t[j - 1]) {
dp[j] += dp[j - 1]
}
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: 子序列計數 DP — 「用」或「不用」當前字元的選擇
- Key trick: 空間優化時必須逆向遍歷以保護舊值；這題和 0/1 背包的逆向遍歷邏輯一致