Java最长公共子序列的动态规划算法

Question

我试图为最长公共子序列写一个动态规划算法。返回应该是这个子序列的长度。但是我的算法总是返回0。我找不到错误。

public static int LCS(String A, String B, int m, int n) {
    int table[][] = new int[m + 1][n + 1];

    for (int i = 0; i < m; i++) {
        table[i][0] = 0;
    }
    for (int i = 1; i < n; i++) {
        table[0][n] = 0;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (A.charAt(i) == B.charAt(j)) {
                table[i][j] = table[i - 1][j - 1] + 1;
            } else {
                table[i][j] = max(table[i][j - 1], table[i - 1][j]);
            }
        }
    }

    return table[m][n];
}

private static int max(int a, int b) {
    return (a > b) ? a : b;
}

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);

    System.out.println("Your input words:\n");
    String x = in.nextLine();
    String y = in.nextLine();

    in.close();

    int m = x.length();
    int n = y.length();

    System.out.println("Length of LCS is " + LCS(x, y, m, n));
}

Answer 1

循环的条件使用

因此，i决不等于m，j决不等于n，所以在这些循环中决不修改表m，对吗？

返回的值是从未修改的table[m][n]处的值：0。

Answer 2

看起来您实现了此算法，但有几个错误：

>

您的循环应该包含1... m和1... n，这意味着您需要更改

charAt（）是基于零的，因此需要charAt（i-1）和charAt（j-1）。

这些不是错误，而是：

>

在Java中，初始化为0的循环是不必要的<代码>表已经由新的运算符初始化为全零。

无需实现max（），因为它已经实现为数学。max（）。

因此，这是使用链接文章中的名称的结果：

public static int LCS(String X, String Y) {
    final int m = X.length();
    final int n = Y.length();
    int[][] C = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (X.charAt(i - 1) == Y.charAt(j - 1))
                C[i][j] = C[i - 1][j - 1] + 1;
            else
                C[i][j] = Math.max(C[i][j - 1], C[i - 1][j]);
    return C[m][n];
}

测试

System.out.println(LCS("This is a test", "Does it work ok?"));

输出

5

以下是最长公共子序列的匹配字母：

This is a test
   ↑↑↑ ↑ ↑
   ↓↓↓ ↓    ↓
Does it work ok?