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

最长公共子序列（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。最后将结果序列反转即为所求的最长公共子序列。

相关问题

使用动态规划算法求两个序列的最长公共子序列，需构造一条最长公共子序列。 输入 每组输入包括两行，每行包括一个字符串。 输出 两个字符序列的一条最长公共子序列。（输入已确保最长公共子序列的唯一性）

以下是使用动态规划算法求解两个序列的最长公共子序列的 Python 代码：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = m, n
    lcs_str = ""
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs_str = s1[i - 1] + lcs_str
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return lcs_str

其中 `s1` 和 `s2` 分别表示两个字符串，函数返回它们的最长公共子序列。在动态规划的过程中，我们使用一个二维数组 `dp` 来记录子问题的最优解，其中 `dp[i][j]` 表示 `s1` 的前 `i` 个字符和 `s2` 的前 `j` 个字符的最长公共子序列长度。在计算 `dp[i][j]` 的过程中，如果 `s1[i-1]` 和 `s2[j-1]` 相等，则 `dp[i][j]` 等于 `dp[i-1][j-1] + 1`，否则 `dp[i][j]` 等于 `max(dp[i-1][j], dp[i][j-1])`。最后，我们可以根据 `dp` 数组和两个字符串构造出最长公共子序列。具体地，从 `dp[m][n]` 开始，如果 `s1[i-1]` 和 `s2[j-1]` 相等，则将这个字符加入到最长公共子序列中，并向左上角移动；如果 `dp[i-1][j]` 大于 `dp[i][j-1]`，则向上移动；否则向左移动。重复这个过程直到 `i` 或 `j` 等于 0。最终返回的 `lcs_str` 就是最长公共子序列。

使用动态规划算法求两个序列的最长公共子序列，需构造一条最长公共子序列。Java代码

以下是使用动态规划算法求两个序列的最长公共子序列并构造一条最长公共子序列的Java代码。

public static int[][] getLCS(char[] str1, char[] str2){
    int[][] dp = new int[str1.length+1][str2.length+1];
    for(int i = 1 ; i <= str1.length ; i++){
        for(int j = 1 ; j <= str2.length ; j++){
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp;
}

public static String getLCSString(char[] str1, char[] str2){
    int[][] dp = getLCS(str1, str2);
    int i = str1.length, j = str2.length;
    Stack<Character> stack = new Stack<Character>();
    while(i > 0 && j > 0){
        if(str1[i-1] == str2[j-1]){
            stack.push(str1[i-1]);
            i--;
            j--;
        }else{
            if(dp[i-1][j] > dp[i][j-1]){
                i--;
            }else{
                j--;
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    while(!stack.isEmpty()){
        sb.append(stack.pop());
    }
    return sb.toString();
}

注：该代码计算的是字符数组的最长公共子序列，如果要计算字符串的最长公共子序列，可以将字符数组作为参数传入该函数。