最長公共子序列 (LCS)

 最長公共子序列 (LCS) 問題的解法，使用動態規劃來找出兩個字串之間的最長公共子序列，並返回該子序列本身及其長度。

程式邏輯解釋

1. 函式定義與初始化

   def lcs(x, y):
       m = len(x)
       n = len(y)
       dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
   

   • x 和 y 是兩個輸入字串。
   • m 和 n 分別表示字串 x 和 y 的長度。
   • dp 是一個二維串列，用來存儲每一步的計算結果。dp[i][j] 代表 x[0..i-1] 和 y[0..j-1] 的最長公共子序列長度。
   • 二維串列 dp 初始化為 (m+1) x (n+1)，全為 0，表示在其中一個字串長度為 0 時，LCS 的長度為 0。

2. 動態規劃填表

   for i in range(1, m+1):
       for j in range(1, n+1):
           if x[i-1] == y[j-1]:
               dp[i][j] = dp[i-1][j-1] + 1
           else:
               dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   

   • 這個雙層迴圈遍歷字串 x 和 y 的每個字符。
   • 比較字母：
     • 如果 x[i-1] 和 y[j-1] 相同，表示字母匹配，則 dp[i][j] = dp[i-1][j-1] + 1，表示這個匹配可以延續上一個匹配子序列的長度。
     • 如果 x[i-1] 和 y[j-1] 不相同，則 dp[i][j] 取 dp[i-1][j] 和 dp[i][j-1] 中的較大值，表示繼續使用先前計算的較長 LCS。

3. 反向追踪求 LCS 字串

   lcs_str = []
   i, j = m, n
   while i > 0 and j > 0:
       if x[i-1] == y[j-1]:
           lcs_str.append(x[i-1])
           i -= 1
           j -= 1
       elif dp[i-1][j] > dp[i][j-1]:
           i -= 1
       else:
           j -= 1
   lcs_str.reverse()
   return ''.join(lcs_str)
   

   • 初始化：i 和 j 設定為字串 x 和 y 的長度，表示從 dp 表格的右下角開始追踪。
   • 追踪邏輯：
     • 如果 x[i-1] 和 y[j-1] 相同，則表示這個字母屬於 LCS。將這個字母加入 lcs_str，並同時將 i 和 j 減 1，向左上方移動。
     • 如果字母不同，則比較上方 dp[i-1][j] 和左方 dp[i][j-1]，選擇較大的方向，向該方向移動。這樣保證沿著 LCS 的路徑前進。
   • 反轉字串：因為反向追踪得到的字母順序是反的，所以最後要使用 reverse()。

4. 測試程式碼與輸出

   x = "ABCDEG"
   y = "BDEF"
   r = lcs(x, y)
   print(r, len(r))
   

   • 設定字串 x = "ABCDEG" 和 y = "BDEF"，調用 lcs 函式計算 LCS 字串。
   • 輸出結果顯示 LCS 字串及其長度。

執行結果：

BDE 3

範例解析

• 字串 x = "ABCDEG" 和 y = "BDEF" 共有的最長公共子序列是 "BDE"，長度為 3。
• 這是因為程式通過動態規劃表格計算了所有可能的子序列長度，並通過反向追踪重建了這個最長公共子序列。

總結

1. 動態規劃表格計算 LCS 長度：二維串列 dp 記錄了字串之間每一步的匹配情況，從而計算出 LCS 的長度。
2. 反向追踪重建 LCS：利用 dp 表格的值反向追踪，找到形成 LCS 的實際字母序列。
3. 時間複雜度：O(m × n)，其中 m 和 n 分別是兩個字串的長度。空間複雜度也是 O(m × n)，因為需要儲存二維串列。