Longest Common Subsequence

最長公共子序列 (LCS) - Dynamic Programming 經典問題

1. 動態規劃 (Dynamic Programming)

• 時間複雜度: O(m * n) 這是計算 LCS 的最常見解法。這裡 m 和 n 分別是兩個字串的長度。需要計算一個 m * n 的 DP 表，並填充每個格子。

• 空間複雜度: O(m * n) 需要 m * n 的 DP 表來存儲每個子問題的解。

2. 空間優化的動態規劃 (Space Optimized Dynamic Programming)

• 時間複雜度: O(m * n) 與基本的動態規劃方法相同，仍然需要填充 m * n 的表格，但這種方法只需要保留當前和前一行的資訊。

• 空間複雜度: O(min(m, n)) 通常使用兩行來表示 DP 表格，並交替更新，所以空間複雜度可以減少到:

  $$O(\min(m, n))$$

3. 遞歸 (Recursive)

• 時間複雜度: O(2^(m + n)) 這是最直接的解法。每次遞歸會有兩個選擇（包括當前字符或跳過當前字符），因此會產生指數級的時間複雜度。

• 空間複雜度: O(m + n) 由於遞歸的深度最多為 m + n，所以空間複雜度為遞歸深度。

4. 回溯 (Backtracking)

• 時間複雜度: O(2^(m + n)) 與純遞歸解法相似，回溯會根據 DP 表中的分支點選擇多個路徑，因此複雜度是指數級的。

• 空間複雜度: O(m + n) 回溯過程會使用額外的空間來存儲路徑，因此空間複雜度與遞歸的深度相同。

5. 帶備忘錄的遞歸 (Memoization / Top-Down DP)

• 時間複雜度: O(m * n) 與動態規劃相同，使用備忘錄避免了重複計算，從而將時間複雜度降低到:

  $$O(m \times n)$$

• 空間複雜度: O(m * n) 需要額外的 m * n 空間來存儲備忘錄。

6. 矩陣法 (Matrix Method)

• 時間複雜度: O(m * n) 與基本的動態規劃方法相同，通過填充一個 m * n 的矩陣來計算 LCS。

• 空間複雜度: O(m * n) 空間複雜度與基本的動態規劃解法相同，仍需要 m * n 的矩陣來存儲 LCS 的長度。

Summary

• 動態規劃是最常見且效率較高的解法，尤其適用於大多數情況。
• 空間優化的動態規劃能在不影響時間複雜度的情況下，顯著減少空間消耗。
• 遞歸和回溯的解法在時間上效率較低，適用於較小的輸入或為了理解問題本質的簡單示範。