LCS（Longest Common Subsequence）方法求 Longest Increasing Subsequence (LIS)

 通過 LCS（Longest Common Subsequence）的方法計算數列的 Longest Increasing Subsequence (LIS)。程式的邏輯如下：

---

程式追踪與講解

1. 輸入數列

x = [1, 3, 5, 7, 9, 8, 6, 2, 4]
y = x[:]
y.sort()

• 輸入數列 x 是原始數列 [1, 3, 5, 7, 9, 8, 6, 2, 4]。
• y 是將 x 排序後的數列 [1, 2, 3, 4, 5, 6, 7, 8, 9]。
• LIS 問題被轉化為在兩個數列 x 和 y 中找到 LCS。

---

2. 初始化 LCS 矩陣

lx = len(x)
ly = len(y)
c = [[0] * (ly + 1) for _ in range(lx + 1)]

• 建立一個大小為 (lx+1) x (ly+1) 的矩陣 c，用於存儲動態規劃的中間結果。
• 初始狀態下，矩陣中的所有值均為 0。

例如：

c = [
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 ...
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

---

3. 計算 LCS 矩陣

for i in range(1, lx + 1):
    for j in range(1, ly + 1):
        if x[i - 1] == y[j - 1]:
            c[i][j] = c[i - 1][j - 1] + 1
        else:
            c[i][j] = max(c[i - 1][j], c[i][j - 1])

• 動態規劃的核心邏輯：

  • 如果 x[i-1] == y[j-1]，則 c[i][j] = c[i-1][j-1] + 1（匹配，長度增加）。
  • 否則，c[i][j] = max(c[i-1][j], c[i][j-1])（取上一行或左邊的最大值）。

• 例子追踪：

  • x[0] = 1，y[0] = 1，相等，c[1][1] = c[0][0] + 1 = 1。
  • x[1] = 3，y[1] = 2，不相等，c[2][2] = max(c[1][2], c[2][1]) = 1。
  • 重複此過程構建完整矩陣。

最終矩陣 c：

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 4]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5]
[0, 1, 1, 2, 2, 3, 3, 4, 5, 5]
[0, 1, 1, 2, 2, 3, 4, 4, 5, 5]
[0, 1, 1, 2, 2, 3, 4, 4, 5, 5]
[0, 1, 1, 2, 3, 3, 4, 4, 5, 5]

---

4. 回溯找到 LIS

lcs = []
i, j = lx, ly
while i > 0 and j > 0:
    if x[i - 1] == y[j - 1]:
        lcs.append(x[i - 1])
        i -= 1
        j -= 1
    elif c[i - 1][j] > c[i][j - 1]:
        i -= 1
    else:
        j -= 1

• 從矩陣右下角開始回溯，找到符合條件的元素：

  • 如果 x[i-1] == y[j-1]，該元素屬於 LIS，加入結果列表，並向左上移動。
  • 否則，選擇較大的值方向移動。

• 最終回溯結果為反向的 LIS，需要反轉。

---

5. 結果處理

lcs = ''.join(map(str, reversed(lcs)))

• 將回溯結果反轉並轉換為字串格式。

---

輸出結果

1. LIS 長度

矩陣的右下角 c[lx][ly] 的值即為 LIS 長度：

LIS 長度: 5

2. LIS 實際內容

反轉後的結果：

LIS 實際內容: 13579

3. LIS 矩陣

LIS 矩陣:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 4]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5]
[0, 1, 1, 2, 2, 3, 3, 4, 5, 5]
[0, 1, 1, 2, 2, 3, 4, 4, 5, 5]
[0, 1, 1, 2, 2, 3, 4, 4, 5, 5]
[0, 1, 1, 2, 3, 3, 4, 4, 5, 5]

---

程式關鍵點

1. 矩陣構建：

   • 通過比較兩個數列 x 和 y，構建動態規劃矩陣。

2. 回溯：

   • 從右下角回溯找到 LIS，並按順序記錄。

3. LIS 與 LCS 的關聯：

   • LIS 是在原數列與其排序後數列之間求 LCS。

該程式完美演示了如何將 LCS 問題轉化為 LIS 問題並求解。