最长公共子序列python3

以下是求解最长公共子序列的Python3代码示例：

def lcs(str1, str2):
    m = len(str1)
    n = len(str2)
    # 初始化二维数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 填充数组
    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])
    # 返回最长公共子序列
    return dp[m][n]

# 测试
str1 = "ABCD"
str2 = "ACDF"
print(lcs(str1, str2)) # 输出：2

上述代码中，我们定义了一个名为`lcs`的函数，该函数接受两个字符串作为输入参数，返回它们的最长公共子序列的长度。在函数内部，我们首先获取两个字符串的长度，然后初始化一个二维数组`dp`，用于存储子问题的解。接着，我们使用两个嵌套的循环遍历两个字符串的所有字符，并根据它们是否相等来更新`dp`数组。最后，我们返回`dp[m][n]`，即两个字符串的最长公共子序列的长度。

相关问题

最长公共子序列python

最长公共子序列可以使用动态规划算法来求解，具体实现如下：

def lcs(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    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])

    return dp[m][n]

其中，dp[i][j]表示str1的前i个字符与str2的前j个字符的最长公共子序列长度。如果str1[i-1]等于str2[j-1]，则dp[i][j]等于dp[i-1][j-1]加上1；否则，dp[i][j]等于dp[i-1][j]和dp[i][j-1]的较大值。

例如，对于字符串str1="ABCDGH"和str2="AEDFHR"，运行lcs(str1, str2)会返回3，表示它们的最长公共子序列为"ADH"。

相同序列最长公共子序列python实现

最长公共子序列（Longest Common Subsequence，简称LCS）是指在两个序列中找到一个最长的子序列，使得该子序列在两个序列中出现的顺序一致，但不要求连续。下面是一个用Python实现最长公共子序列的示例：

def longest_common_subsequence(seq1, seq2):
    m = len(seq1)
    n = len(seq2)
    
    # 创建一个二维数组来存储中间结果
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    # 填充二维数组，计算LCS的长度
    for i in range(1, m+1):
        for j in range(1, n+1):
            if seq1[i-1] == seq2[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
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if seq1[i-1] == seq2[j-1]:
            lcs.append(seq1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    # 反转LCS得到最终结果
    lcs.reverse()
    return lcs

# 示例用法
seq1 = "ABCDGH"
seq2 = "AEDFHR"
lcs = longest_common_subsequence(seq1, seq2)
print("Longest Common Subsequence:", "".join(lcs))

在这个示例中，我们定义了一个`longest_common_subsequence`函数，它接受两个序列`seq1`和`seq2`作为输入。函数使用动态规划的方法计算LCS的长度，并构建LCS序列。

在主程序中，我们使用示例输入序列`"ABCDGH"`和`"AEDFHR"`来测试`longest_common_subsequence`函数，并打印最长公共子序列。

运行上述代码，输出结果将是：

Longest Common Subsequence: ADH

这表示序列`"ADH"`是`"ABCDGH"`和`"AEDFHR"`的最长公共子序列。

希望这个示例对你有帮助！如果你还有其他问题，请随时提问。