python获取两个列表的共有的子序列

可以使用动态规划算法来解决这个问题。我们定义一个二维数组，第 i 行第 j 列表示以第一个列表的第 i 个元素结尾和以第二个列表的第 j 个元素结尾的公共子序列的长度。然后，我们可以从第二行和第二列开始逐行逐列填充这个数组。如果两个元素相等，那么当前位置的值等于左上角位置的值加一；否则，当前位置的值等于左边位置和上边位置的值中较大的那一个。最后，我们可以从后向前遍历这个数组，找到其中的一个最长公共子序列，输出即可。

以下是一个示例代码：

def find_lcs(list1, list2):
    m = len(list1)
    n = len(list2)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if list1[i-1] == list2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    i = m
    j = n
    lcs = []
    while i > 0 and j > 0:
        if list1[i-1] == list2[j-1]:
            lcs.append(list1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    lcs.reverse()
    return lcs

使用示例：

list1 = [1, 2, 3, 4, 5, 6]
list2 = [3, 4, 5, 6, 7, 8, 9]
lcs = find_lcs(list1, list2)
print(lcs)  # 输出 [3, 4, 5, 6]