私は、LCSの問題のための2つの入力文字列持つテーブル

Question

から最長共通部分を見つける： 1：ABCDGH 2：AEDFHR

次の表は、長さのためのボトムアップテーブルへの動的プログラミングソリューションを表し、 LCSの：LCSの実際の文字を検索しようと、あなたがテーブルの端から開始し、後方に行くthis videoで提供される方法に基づき

。左右のセルが現在のセルと同じでなく、セルの対角が1つ小さい場合、現在の列の文字が含まれていることがわかり、斜めに戻ってきます。それ以外の場合は、左または右に移動します。

この方法に従えば、この一連の動き（H、R）、（H、H）、そして（F、G）があります。しかし、いったんそこに着くと、アルゴリズムはどのようにして次の場所に行くのですか？次の列からLCSに「D」が含まれるようになるので左に移動する必要がありますが、（F、G）の左、右、対角のセルはすべて2の値を持ちます対角線上のセルは1つ少ない。 同じ値で囲まれたセルがある場合、アルゴリズムのロジックはどうなるべきですか？

Answer 1

動的プログラミングの問題には、複数の最適解があることがよくあります。 2つまたは3つの隣接するセルが同じ値を有する場合、それらは同じように良好であり、その値が隣接するセルの中でも最良のものである場合、それらのいずれかにジャンプすることによって最適解の1つにつながる。 （問題のステートメントは、複数の最適解がある場合は、できるだけ早く最後の置換を選択するなどの追加の制約を課す可能性があります）。