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

看起来你实现了这个算法，但是有一些错误：

• 您的循环应该是

  1..m

  和

  1..n

  包含，这意味着您需要将

  <

  更改为

  <=

  。

• charAt()

  是从零开始的，因此您需要

  charAt(i - 1)

  和

  charAt(j - 1)

  。

这些不是错误，而是：

• Java 中不需要循环初始化为 0。

  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

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

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

Answer 2

for

循环中的条件使用

i < m

或

j < n

。

因此

i

永远不会等于

m

并且

j

永远不会等于

n

，所以

table[m][n]

永远不会在这些循环中被修改，对吗？

返回的值是

table[m][n]

处的值，从未被修改：

0

。

Answer 3

// LCS = 最长公共子序列 公共级濒海战斗舰{

// method 1 : Recursion ...Overlapping Sub-problems ...O(2^N)
public int lengthLCS( char[] s1, char[] s2, int m, int n){

    if(m==0 || n==0)
        return 0;
    else if(s1[m-1] == s2[n-1])
        return 1 + lengthLCS(s1, s2, m-1, n-1);
    else
        return Math.max(
                lengthLCS(s1, s2, m-1, n),
                lengthLCS(s1, s2, m, n-1));
}

// method 2 : Tabulation ...Top-Down DP ...O(MN)
public int lcsDP( char[] X, char[] Y, int m, int n){
    int L[][] = new int[m+1][n+1];

    for(int i=0; i<=m; i++)
        L[i][0] = 0;

    for(int j=0; j<=n; j++)
        L[0][j] = 0;

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(X[i-1] == Y[j-1])
                L[i][j] = 1 + L[i-1][j-1];
            else
                L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
        }
    }
    return L[m][n];
}

// Reference: DSA in Java : Goodrich
/* Returns table such that L[j][k] is length of LCS for X[0..j−1] and Y[0..k−1]. */
public int[][] lcsTable(char[] X, char[] Y, int m, int n) {

    int[][] L = new int[m+1][n+1];
    for (int j=0; j < m; j++)
        for (int k=0; k < n; k++)
            if (X[j] == Y[k])  // align this match
                L[j+1][k+1] = L[j][k] + 1;
            else                // choose to ignore one character
                L[j+1][k+1] = Math.max(L[j][k+1], L[j+1][k]);
    return L;
}

/* Returns the longest common substring of X and Y, given LCS table L. */
public String reconstructLCS(char[] X, char[] Y, int[][] L) {

    StringBuilder solution = new StringBuilder();
    int j = X.length;
    int k = Y.length;
    while (L[j][k] > 0)          // common characters remain
        if (X[j-1] == Y[k-1]) {
            solution.append(X[j - 1]);
            j--;
            k--;
        }else if(L[j-1][k] >= L[j][k-1])
            j--;
        else
            k--;

    // return left-to-right version, as String
    return solution.reverse().toString();
}

// memory efficient : better space complexity O(N)
public int lcsOptimized(String X, String Y) {
    int[] L = new int[Y.length()+1];
    int n = L.length;
    for(int i = 0; i< X.length(); i++){
        int prev = L[0];
        for(int j = 1; j < n; j++){
            int temp = L[j];
            if(X.charAt(i) != Y.charAt(j-1))
                L[j] = Math.max(L[j-1], L[j]);
            else
                L[j] = prev +1;
            prev = temp;
        }
    }
    return L[n-1];
}

public static void main(String[] args) {

    // 2 DNA Sequences

    String str1="GTTCCTAATA";     //   AXYZ
    String str2="CGATAATTGAGA";   //   BAZ

    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();

    LCS lcs = new LCS();

    int lcsLength = lcs.lengthLCS(s1, s2, s1.length, s2.length);

    int lcsDpLength = lcs.lcsDP(s1, s2, s1.length, s2.length);

    int lcsDpLengthOptimized = lcs.lcsOptimized(str1, str2);

    int[][] table = lcs.lcsTable(s1, s2, s1.length, s2.length);

    String longestCommonSubsequence = lcs.reconstructLCS(s1, s2, table);

    System.out.println("String1 ="+str1);
    System.out.println("String2 ="+str2);
    System.out.println("Length of Longest Common Subsequence = "+lcsLength);
    System.out.println("Length of LCS using DP Tabulation    = "+lcsDpLength);
    System.out.println("Length of LCS using DP Optimized Tabulation = "+lcsDpLengthOptimized);

    System.out.println("Longest Common Subsequence = "+longestCommonSubsequence);
}

}