归求最长公共子序列和构造最长公共子序列的算法

最长公共子序列（LCS）问题是指给定两个序列X和Y，找出它们最长的公共子序列。常用的解决LCS问题的算法有递归求解和动态规划。

递归求解算法的思路是：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。递归调用使i或j减1，因此算法的计算时间为O(m+n)。

动态规划算法的思路是：创建DP数组C[ ] [ ]，把首行和首列置零，按照以下规则把表填满，C=5即为所要求的最长公共子序列的长度。动态规划算法的时间复杂度也为O(mn)。

构造最长公共子序列的方法是：从DP数组的右下角开始，如果X[m]=Y[n]，则将X[m]加入到结果序列中，同时i和j都减1；否则，如果C[i-1][j]>C[i][j-1]，则i减1，否则j减1。重复上述步骤直到i或j为0。最后将结果序列反转即为所求的最长公共子序列。

相关问题

求最长公共子序列 java

最长公共子序列问题是指给定两个字符串，求它们的最长公共子序列。Java中可以使用动态规划算法来解决该问题。具体步骤如下：
1. 定义一个二维数组c[][]来记录最长公共子序列的长度，定义一个二维数组b[][]来记录最长公共子序列的长度的来源。
2. 初始化，将c[][]第一行第一列元素全部赋值为0。
3. 循环阶段，采用自底向上的方式逐步计算最优解。具体来说，对于每个i和j，如果s1[i-1]等于s2[j-1]，则c[i][j]=c[i-1][j-1]+1，并记录最优策略来源b[i][j]=1；否则，公共子序列的长度来源于c[i][j-1]和c[i-1][j]的最大值，根据来源记录最优策略来源b[i][j]。
4. 构造最优解，根据最优决策信息数组b[][]递归构造最优解，即输出最长公共子序列。

Java代码如下所示（假设输入的两个字符串分别为s1和s2）：

int len1 = s1.length();
int len2 = s2.length();
int[][] c = new int[len1+1][len2+1];
int[][] b = new int[len1+1][len2+1];
for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
        if (s1.charAt(i-1) == s2.charAt(j-1)) {
            c[i][j] = c[i-1][j-1] + 1;
            b[i][j] = 1;
        } else if (c[i][j-1] >= c[i-1][j]) {
            c[i][j] = c[i][j-1];
            b[i][j] = 2;
        } else {
            c[i][j] = c[i-1][j];
            b[i][j] = 3;
        }
    }
}
StringBuilder sb = new StringBuilder();
int i = len1, j = len2;
while (i > 0 && j > 0) {
    if (b[i][j] == 1) {
        sb.append(s1.charAt(i-1));
        i--;
        j--;
    } else if (b[i][j] == 2) {
        j--;
    } else {
        i--;
    }
}
String lcs = sb.reverse().toString();

最长公共子序列算法问题python实现

最长公共子序列（Longest Common Subsequence，简称LCS）是一种常见的字符串匹配问题，可以用动态规划算法来解决。下面是一个Python实现的例子：

def longest_common_subsequence(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])
    
    # 构造最长公共子序列
    lcs = ""
    i, j = m, n
    while i > 0 and j > 0:
        if str1[i - 1] == str2[j - 1]:
            lcs = str1[i - 1] + lcs
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return lcs

str1 = "ABCD"
str2 = "ACDF"
lcs = longest_common_subsequence(str1, str2)
print("最长公共子序列为:", lcs)  # 输出：ACD

这段代码使用了一个二维数组`dp`来记录最长公共子序列的长度，然后通过回溯的方式构造出最长公共子序列。其中，`dp[i][j]`表示`str1`的前`i`个字符和`str2`的前`j`个字符的最长公共子序列的长度。