最长公共子序列Java代码

以下是求解最长公共子序列的Java代码实现：

public class LongestCommonSubsequence {
    public static int lcs(char[] X, char[] Y, int m, int n) {
        int[][] L = new int[m+1][n+1];
 
        for (int i=0; i<=m; i++) {
            for (int j=0; j<=n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X[i-1] == Y[j-1])
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
            }
        }
        return L[m][n];
    }
 
    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";
 
        char[] X=s1.toCharArray();
        char[] Y=s2.toCharArray();
        int m = X.length;
        int n = Y.length;
 
        System.out.println("Length of LCS is "+ lcs( X, Y, m, n ) );
    }
}

这段代码使用了动态规划的思想，通过构造一个二维数组L来存储两个字符串的最长公共子序列的长度。L[i][j] 表示 X[0..i-1] 和 Y[0..j-1] 的最长公共子序列的长度。在构造L数组时，如果 X[i-1] 等于 Y[j-1]，则L[i][j] = L[i-1][j-1] + 1，否则 L[i][j] = max(L[i-1][j], L[i][j-1])，最终L[m][n] 就是两个字符串的最长公共子序列的长度。