最长公共子序列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

最长公共子序列（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；否则取当前行和当前列中较大值。

最长公共子序列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"。