2.给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。Java代码完整

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

public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String X = "ABCBDAB";
        String Y = "BDCABA";
        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1]; // dp数组
        // 初始化dp数组
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.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]);
                }
            }
        }
        // 输出最长公共子序列
        int len = dp[m][n];
        char[] lcs = new char[len];
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                lcs[--len] = X.charAt(i - 1);
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        System.out.println("Longest Common Subsequence: " + new String(lcs));
    }
}

其中，`X`和`Y`分别表示两个序列，`dp`数组存储最长公共子序列的长度，`lcs`数组用于记录最长公共子序列。在填充`dp`数组的过程中，如果`X[i-1]==Y[j-1]`，则`dp[i][j]=dp[i-1][j-1]+1`，表示当前字符在最长公共子序列中；否则，`dp[i][j]=max(dp[i-1][j], dp[i][j-1])`，表示当前字符不在最长公共子序列中。最后，从`dp`数组的右下角开始，通过回溯求出最长公共子序列。