求最长公共子序列 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();