最长公共子序列算法 java

最长公共子序列（Longest Common Subsequence，LCS）问题是指给定两个字符串，求它们的最长公共子序列。下面是一个简单的Java实现：

public class LCS {
    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "ABCD";
        String s2 = "ACDF";
        System.out.println(lcs(s1, s2)); // 输出 2
    }
}

在这个实现中，我们使用动态规划来解决问题。我们定义一个二维数组`dp`，其中`dp[i][j]`表示`s1`的前`i`个字符和`s2`的前`j`个字符的最长公共子序列的长度。然后，我们使用一个双重循环来填充`dp`数组。具体来说，如果`s1`的第`i`个字符和`s2`的第`j`个字符相同，那么最长公共子序列的长度就是前面的最长公共子序列的长度加1，即`dp[i-1][j-1]+1`；如果不相同，那么最长公共子序列的长度就是`s1`的前`i-1`个字符和`s2`的前`j`个字符的最长公共子序列的长度、或者`s1`的前`i`个字符和`s2`的前`j-1`个字符的最长公共子序列的长度中的较大值，即`Math.max(dp[i-1][j], dp[i][j-1])`。最后，`dp[m][n]`就是`s1`和`s2`的最长公共子序列的长度。