如何使用Python算法有效地计算两个字符串之间的最长公共子序列（LCS）？

在Python中，可以使用动态规划（Dynamic Programming）来有效地计算两个字符串之间的最长公共子序列（LCS）。下面是一个经典的斐波那契表方法实现：

def longest_common_subsequence(str1, str2):
    m = len(str1)
    n = len(str2)

    # 创建一个二维列表来存储中间结果
    lcs_table = [[0] * (n + 1) for _ in range(m + 1)]

    # 遍历两个字符串，填充lcs_table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:  # 如果字符匹配
                lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1
            else:
                lcs_table[i][j] = max(lcs_table[i - 1][j], lcs_table[i][j - 1])  # 取最大值

    # 最终的最长公共子序列就是最后一行最后一列的值
    return lcs_table[m][n]

# 示例
str1 = "ABCDGH"
str2 = "AEDFHR"
print(longest_common_subsequence(str1, str2))  # 输出：3

这个算法的工作原理是，对于每个位置 `(i, j)`，如果 `str1` 的第 `i` 个字符和 `str2` 的第 `j` 个字符相等，那么它们就共同构成了长度为 `lcs_table[i-1][j-1]+1` 的子序列；如果不相等，则较长的前缀子序列构成的长度即为 `lcs_table[i-1][j]` 和 `lcs_table[i][j-1]` 中的最大值。