java - Java最长公共(public)子序列的动态规划算法

Question

我正在尝试为最长公共(public)子序列编写一个动态规划算法。返回应该是这个子序列的长度。但是我的算法总是返回 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

看起来你实现了 this algorithm ，但有一些错误:

• 你的循环应该是1..m和 1..n 包含，意味着你需要改变<至 <= .

• charAt()是零基础的，所以你需要charAt(i - 1)和 charAt(j - 1) .

这些不是错误，而是:

• 初始化为 0 的循环在 Java 中是不必要的。 table已由 new 初始化为全零运营商。

• 无需实现max() ，因为它已经实现为 Math.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

这里是最长公共(public)子序列的匹配字母:

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