最長公共子序列lcs 1

最長公共子序列（Longest Common Subsequence，LCS）是一種在計算機科學和運籌學中常見的問題，通常用於尋找兩個或多個序列之間的最長共享部分。以下是一種常見的LCS問題的Python實現方式，這個問題的關鍵在於如何利用動態規劃的方法。

這個問題可以通過編寫一個遞歸函式或者使用動態規劃矩陣解決。在這個問題中，我們通常會使用動態規劃矩陣來解決。

以下是使用動態規劃矩陣解決LCS問題的Python代碼：

def lcs(X, Y):
    m = len(X)
    n = len(Y)

    # 創建一個二維數組來存儲LCS的長度
    L = [[0 for x in range(n+1)] for x in range(m+1)]

    # 填充L數組
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])

    # 找出L的最大值，就是LCS的長度
    lcs_len = L[m][n]

    # 通過索引逆序恢復出LCS序列
    return ''.join([X[i-lcs_len][j] for i, j in enumerate(L[m][n])])

這段代碼首先創建一個二維數組L，用於存儲最長公共子序列的長度。然後通過遍歷X和Y的每一個元素，檢查是否在相同的子序列中，如果是，則將當前位置的元素值加一，否則選擇左邊或者上邊的元素的最大值。最後通過遍歷數組中的最大值索引，就可以恢復出最長公共子序列。

這個算法的時間複雜度是O(mn)，其中m和n分別是X和Y的長度。這個算法的空間複雜度也是O(mn)。

需要注意的是，這段代碼只返回最長公共子序列本身，如果你還需要找出每對對應字元的最長公共子序列的位置，你需要進行額外的操作。例如，可以使用兩層循環來找到每一對對應字元在原序列中的位置，或者可以使用棧結構來實現這個功能。