最长公共子序列问题的代码

以下是Python中求解最长公共子序列问题的代码：

def lcs(X, Y):
    # 获取字符串长度
    m = len(X)
    n = len(Y)
    # 初始化二维数组
    L = [[None]*(n+1) for i in range(m+1)]
    # 填充L数组
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    # 返回LCS的长度
    return L[m][n]

该代码使用动态规划算法解决最长公共子序列问题。其中，X和Y分别为两个字符串，m和n分别为它们的长度。L是一个二维数组，用于存储子问题的解。在填充L数组时，如果X和Y的当前字符相同，则L[i][j]等于L[i-1][j-1]+1；否则，L[i][j]等于L[i-1][j]和L[i][j-1]中的较大值。最后，返回LCS的长度。

相关问题

C++最长公共子序列问题代码

以下是一个求解最长公共子序列问题的 C 语言代码示例：

#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 100

int max(int a, int b) {
    return (a > b) ? a : b;
}

int lcs(char* str1, char* str2, int len1, int len2) {
    int dp[MAX_LENGTH][MAX_LENGTH];

    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else 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[len1][len2];
}

int main() {
    char str1[MAX_LENGTH], str2[MAX_LENGTH];
    scanf("%s %s", str1, str2);

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    int result = lcs(str1, str2, len1, len2);
    printf("The length of longest common subsequence is %d\n", result);

    return 0;
}

这个程序中，函数 `lcs` 用于计算两个字符串的最长公共子序列。使用动态规划的思想，通过建立一个二维数组 `dp` 来保存中间结果。数组中的每个元素 `dp[i][j]` 表示字符串 `str1` 的前 `i` 个字符和字符串 `str2` 的前 `j` 个字符的最长公共子序列长度。如果 `str1[i-1] == str2[j-1]`，则当前字符在两个字符串中都存在，可以将最长公共子序列长度加一，否则将当前字符从其中一个字符串中去掉，取两种情况中的较大值作为最长公共子序列的长度。最终返回 `dp[len1][len2]`，即两个字符串的最长公共子序列长度。

注意事项：

- 本程序中的最长公共子序列要求不需要连续，如果需要连续，则需要改变动态规划的状态转移方程。
- 在输入字符串时，要保证字符串的长度不超过 `MAX_LENGTH`，否则可能会导致数组越界。
- 在实际应用中，为了避免字符串的长度过大，需要对算法进行优化，比如使用滚动数组等技巧。

动态规划法求解最长公共子序列问题代码

以下是Python实现的最长公共子序列问题的动态规划算法代码：

def lcs(X, Y):
    # 创建一个二维数组，用于存储LCS的长度
    m = len(X)
    n = len(Y)
    L = [[0] * (n + 1) for i in range(m + 1)]
     
    # 填充LCS长度矩阵
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
     
    # LCS的长度即为L[m][n]
    index = L[m][n]
 
    # 从LCS长度矩阵中反向查找LCS
    lcs = [""] * (index+1)
    lcs[index] = ""
 
    i = m
    j = n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs[index-1] = X[i-1]
            i -= 1
            j -= 1
            index -= 1
        elif L[i-1][j] > L[i][j-1]:
            i -= 1
        else:
            j -= 1
 
    return "".join(lcs[1:])

其中，`X`和`Y`是要计算最长公共子序列的两个字符串。函数返回值是一个字符串，表示这两个字符串的最长公共子序列。