題目描述:給定兩個字串 text1 和 text2,回傳它們的最長公共子序列(LCS)的長度。子序列不需要連續。
解題思路:經典 2D DP。定義 dp[i][j] 為 text1[0..i-1] 和 text2[0..j-1] 的 LCS 長度。若 text1[i-1] == text2[j-1],則 dp[i][j] = dp[i-1][j-1] + 1(兩字元匹配,加 1);否則 dp[i][j] = max(dp[i-1][j], dp[i][j-1])(跳過某一側的字元)。
時間複雜度:O(m × n) — 填充整個 DP 表格。
空間複雜度:O(m × n) — 可優化為 O(min(m, n)) 只保留兩行。
1. Create dp table of size (m+1) x (n+1), initialized to 0 2. For i from 1 to m, j from 1 to n: a. If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 b. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 3. Return dp[m][n]
遞迴無記憶 O(2^(m+n)) 最壞:嘗試所有配對,重複計算。
空間優化 O(min(m,n)):使用單行 DP,滾動陣列 — 時間複雜度相同但空間減半。