python求最长公共子序列问题，要求具体最长公共子序列

在Python中，求两个字符串的最长公共子序列（Longest Common Subsequence, LCS）通常使用动态规划（Dynamic Programming）算法来解决。这个算法的基本思想是通过构建一个二维数组来存储已计算出的子序列长度，然后逐步填充这个数组，最终找到两个字符串中最长的公共部分。

下面是一个简单的Python函数，名为`lcs`，它接受两个字符串作为输入，并返回它们的最长公共子序列：

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

    # 初始化一个m+1 x n+1 的二维数组
    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就是dp数组右下角的值
    result = ''
    i, j = m, n
    while i > 0 and j > 0:
        if str1[i - 1] + result
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return result

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

在这个例子中，最长公共子序列是"ADH"。