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

あなたが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]; 
} 

TEST

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

OUTPUT

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です。