最长公共子序列问题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];
}