dynamic-programming - 動的プログラミング

Question

Longest Common Subsequence Problem の解決策を誰か説明してくれませんか? 具体的には、再帰関係は

if(x _i =y _j ) then answer= max _L (i-1, j-1) +1

else answer=Max{Max _L (i-1, j), Max _L (i, j-1)}

x _i / y _iは構築されたテーブルの文字です。Max _Lは、構築されたテーブルのエントリに対応します。

私の質問は、なぜ答えが maxL(i-1,j-1) + 1 なのですか? 文字が一致する場合にのみ、左上の対角線から追加する必要があるのはなぜですか? ありがとうございました

Answer 1

再帰関係の (xi=yj) は、両方の文字列がそれぞれの現在の位置に同じ文字を持っていることを意味します。

簡単な例を見てみましょう：

入力文字列AGGTABとGXTXAYBについて考えてみます。

両方の文字列の最後の文字が'B'一致します。[つまり、xi==yj 条件が成立します]。

したがって、LCS の長さは次のように記述できます。

LCS("AGGTAB", "GXTXAYB") = 1 + LCS("AGGTA", "GXTXAY")

LCS("AGGTA", "GXTXAY") は Table[i−1,j−1] (つまり max _L [i-1][j-1])に格納されます。