输出最长公共子序列java

最长公共子序列问题可以使用动态规划来解决。具体来说，可以定义一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列的长度。则有以下状态转移方程：

if (s1[i-1] == s2[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]);
}

最终的答案即为dp[s1.length()][s2.length()]。下面是完整的Java代码实现：

public static String longestCommonSubsequence(String s1, String s2) {
int[][] dp = new int[s1.length()+1][s2.length()+1];
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i-1) == s2.charAt(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]);
}
}
}
StringBuilder sb = new StringBuilder();
int i = s1.length(), j = s2.length();
while (i > 0 && j > 0) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
sb.append(s1.charAt(i-1));
i--;
j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}