最长公共子序列Python

最长公共子序列（Longest Common Subsequence, LCS）是指两个或多个序列中最长的公共部分。在Python中，你可以使用动态规划算法来计算两个字符串的LCS。下面是一个简单的示例：

def lcs(str1, str2):
    m = len(str1)
    n = len(str2)
    
    # 初始化一个二维列表用于存储中间结果
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    # 遍历字符串，填充dp矩阵
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 返回LCS长度
    return dp[m][n]

# 示例
str1 = "ABCDGH"
str2 = "AEDFHR"
print("最长公共子序列:", lcs(str1, str2))

在这个例子中，`lcs`函数首先创建一个二维数组`dp`，其中`dp[i][j]`表示`str1[:i]`和`str2[:j]`的最长公共子序列的长度。然后逐行和逐列遍历这两个字符串，如果对应字符相同，则将上一行、上一列的值加1；否则取当前行和当前列中较大值。