python求最长公共子序列问题

Python中求解最长公共子序列（Longest Common Subsequence, LCS）问题通常采用动态规划的方法。动态规划是一种通过把复杂问题分解成更小的子问题来解决的算法。对于LCS问题，我们创建一个二维数组，数组的每个元素表示两个输入序列到当前位置为止的最长公共子序列的长度。

以下是使用Python编写的解决方案：

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

    # 初始化一个矩阵，第一行和第一列的值为0，因为一个空串与另一个非空串的LCS长度为0
    L = [[0] * (n + 1) for _ in range(m + 1)]

    # 遍历矩阵填充值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:  # 如果字符相等
                L[i][j] = L[i - 1][j - 1] + 1  # 则当前位置的LCS长度等于上一个位置的长度加1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])  # 否则，取前一个和左上角的最大值

    return L[m][n]

# 示例
X = "ABCBDAB"
Y = "BDCAB"
print("最长公共子序列长度:", lcs(X, Y))

在这个例子中，函数`lcs()`接收两个字符串`X`和`Y`作为输入，并返回它们的最长公共子序列的长度。如果需要获取实际的子序列，可以在填写完矩阵后回溯来构建它。