最长公共子序列问题 java

最长公共子序列（Longest Common Subsequence，LCS）问题是指：给定两个字符串S1和S2，求它们的最长公共子序列。

子序列是指在原序列中不改变字符的相对顺序的情况下删除任意个字符（也可以不删），得到的新序列。

例如，字符串S1 = "ABCD"和字符串S2 = "BDAC"的最长公共子序列为"BD"。

在Java中，最长公共子序列问题可以通过动态规划算法来解决。具体来说，可以使用一个二维数组dp[i][j]来记录S1的前i个字符与S2的前j个字符的最长公共子序列长度。

状态转移方程为：

如果S1[i] == S2[j]，则dp[i][j] = dp[i-1][j-1] + 1；
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[S1.length()][S2.length()]就是S1和S2的最长公共子序列长度。

相关问题

最长公共子序列问题java

最长公共子序列问题是指给定两个序列，找到它们最长的公共子序列的长度。在动态规划中，我们可以使用一个二维数组来存储两个序列的所有可能的子问题的解，然后根据这些子问题的解来计算最终的最优解。具体来说，我们可以使用一个二维数组c来存储两个序列的最长公共子序列的长度，其中c[i][j]表示序列A的前i个元素和序列B的前j个元素的最长公共子序列的长度。在计算c[i][j]时，我们可以根据A[i]和B[j]是否相等来判断是否需要进一步解决子问题。如果相等，则c[i][j] = c[i-1][j-1] + 1；否则，c[i][j] = max(c[i-1][j], c[i][j-1])。最终的最长公共子序列的长度就是c[m][n]，其中m和n分别是序列A和序列B的长度。

Java中可以使用二维数组来实现最长公共子序列问题的动态规划算法。具体实现可以参考以下代码：

public static int lcs(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    int[][] c = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
            }
        }
    }
    return c[m][n];
}

最长公共子序列算法 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`的最长公共子序列的长度。