dynamic-programming
サブシーケンス関連アルゴリズム
サーチ…
最長共通サブシーケンス
ダイナミックプログラミングの最も重要な実装の1つは、 最長共通サブシーケンスを見つけることです。最初にいくつかの基本的な用語を定義しましょう。
サブシーケンス：
サブシーケンスは、残りの要素の順序を変更せずにいくつかの要素を削除することによって、別のシーケンスから派生できるシーケンスです。文字列ABCがあるとします。この文字列からゼロまたは1つ以上の文字を消去すると、この文字列の部分列が得られます。したがって、文字列ABCの部分列は{ "A" 、 "B" 、 "C" 、 "AB" 、 "AC" 、 "BC" 、 "ABC" 、 " }}になります。すべての文字を削除しても、空文字列は部分列になります。サブシーケンスを見つけるには、文字列の各文字について、我々は文字を取るか、そうでないかの2つの選択肢があります。したがって、文字列の長さがnの場合 、その文字列の2 n個の部分列があります。
最長共通サブシーケンス：
名前が示すように、2つの文字列の間のすべての共通部分配列のうち、最も長い共通部分配列（LCS）は、最大長を持つものです。例えば：「HELLOM」および「HMLD」との間の共通部分列は「HL」、「HM」などここで、「HLL」、「H」であり、長さ3を有し、最長共通サブシーケンスです。
ブルートフォース方式：
バックトラッキングを使用して2つの文字列のすべての部分列を生成することができます。次に、それらを比較して共通の部分列を見つけることができます。最大の長さのものを見つける必要があるでしょう。私たちはすでに、長さnの文字列の2 n個の部分列があることを見てきました。私たちのnが20-25を超える場合、問題を解決するには数年かかるでしょう。
動的プログラミング方法：
私たちの方法に例をあげてみましょう。 2つの文字列abcdafとacbcfがあるとします。これらをs1とs2としましょう。したがって、これらの2つの文字列の中で最も長い共通部分列は、長さが4の"abcf"になります。もう一度言いますが、部分列は文字列内で連続である必要はありません。 "abcf"を構築するには、 s1の "da"とs2の "c"を無視しました。ダイナミックプログラミングを使用してこれをどのように見つけ出しますか？
まず、行のs1のすべての文字とs2のすべての文字を列に持つテーブル（2D配列）から始めます。ここでは、テーブルは0でインデックス付けされており、1から順番に文字を配置します。各行の左から右へテーブルを移動します。私たちのテーブルは次のようになります：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
ここで、各行と列は、2つの文字列間の最長の共通部分列の長さを表し、その行と列の文字を取り、前の接頭辞に追加するとします。例： Table [2] [3]は、 "ac"と"abc"の間の最も長い共通部分列の長さを表します。
0番目の列は、 s1の空の部分列を表す。同様に、0行目はs2の空の部分列を表す。文字列の空の部分列を取り、別の文字列と一致させようとすると、2番目の部分文字列の長さに関係なく、共通部分列の長さは0になります。したがって、0番目の行と0番目の列を0で埋めることができます。我々が得る：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
さぁ、始めよう。 テーブル[1] [1]を塗りつぶすときに、文字列aと文字列aがあり、それ以外の文字列があれば、ここで最も長い共通部分列は何でしょうか？ここでLCSの長さは1になります。次に表[1] [2]を見てみましょう。文字列abと文字列aがあります。 LCSの長さは1になります。ご覧のとおり 、 abcd 、 abcda 、 abcdafの文字列aのみを考慮しているため、残りの値も1行目に1となります。だから私たちのテーブルは次のようになります：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
行2の場合、これにはcが含まれます 。 表[2] [1]については、片側にはacがあり、反対側にはaがあります。 LCSの長さは1です。これはどこから取得しましたか？上から、2つの部分文字列の間のLCS aを示します。したがって、 s1 [2]とs2 [1]が同じでない場合、LCSの長さは、 上端または左端のLCSの長さの最大値になります。最上部のLCSの長さを取ることは、現在の文字をs2からとらないことを意味します。同様に、左のLCSの長さを取ることは、LCSを作成するためにs1から現在の文字を取得しないことを示します。我々が得る：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
最初の数式は次のようになります。
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
テーブル[2] [2]については、文字列abとacがあります。 cとbは同じではないので、ここでは上または左の最大値を設定します。この場合、再び1です。その後、 表[2] [3]に対して、文字列abcとacがあります。今回は、行と列の両方の電流値が同じです。今度はLCSの長さはLCSの最大長と今までの+ 1の長さに等しくなります。これまでのLCSの最大長はどうでしたか？対角の値をチェックします。これは、 abとaの最適な一致を表します。この状態から、現在の値について、同じように起こったs1とs2にもう1つの文字を追加しました。 LCSの長さはもちろん増加します。 表[2] [3]に1 + 1 = 2を入れます。我々が得る、
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
だから私たちの2番目の式は次のようになります
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
両方のケースを定義しました。これらの2つの公式を使用して、テーブル全体を読み込むことができます。テーブルを埋めると、次のようになります。
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1とs2との間のLCSの長さは、 Table [5] [6] = 4となる 。ここで、5と6はそれぞれs2とs1の長さです。私たちの疑似コードは次のようになります：
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
このアルゴリズムの時間複雑度は次のとおりです。O（mn）ここで、 mとnは各文字列の長さです。
最長の共通部分列をどのように見つけ出すか？右下隅から始めます。私たちは価値がどこから来ているかをチェックします。 表[i-1] [j-1]がTable [i] [j] -1と等しい場合、 s2 [i]またはs1 [j] （両方同じです）、斜めに移動します。値が上から来る場合、つまりTable [i-1] [j]がTable [i] [j]と等しい場合は、先頭に移動します。値が左から来る場合、つまりTable [i] [j-1]がTable [i] [j]と等しい場合は、左に移動します。一番左または一番上の列に達すると、検索が終了します。スタックから値をポップして印刷します。擬似コード：
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
点に留意すべき：[I] [J-1] 表に等しい表[I-1]〜[J]とテーブルの両方場合は[I] [J]と表[I-1] [J-1]ではありませんTable [i] [j] -1と等しい場合、その瞬間に2つのLCSが存在する可能性がある。この擬似コードはこの状況を考慮しません。複数のLCSを見つけるには、これを再帰的に解かなければなりません。
このアルゴリズムの時間複雑度は、 O（max（m、n））である 。
最長増加サブシーケンス
タスクは、指定された整数の配列内で最も長いサブシーケンスの長さを見つけて、サブシーケンスのすべての要素が昇順にソートされるようにすることです。例えば、 { 15,27,14,38,26,55,46,65,85 }の最長増加サブシーケンス（LIS）の長さは6であり、最長増加サブシーケンスは{15,27,38,55、 65、85} 。ここでも、 {3、4、 -1、0、6、2、3 } LISの長さは4であり、部分列は{-1,0,2,3}である 。この問題を解決するために動的プログラミングを使用します。
2番目の例を考えてみましょう： Item = {3, 4, -1, 0, 6, 2, 3} 。まず、シーケンスと同じサイズの配列dpを取ることから始めます。 dp [i]は、元のシーケンスのi番目の項目を含めると、LISの長さを表します。最初の時点で、各アイテムごとに、少なくとも最長増加するサブシーケンスの長さが1であることがわかります。それは単一の要素自体を考慮することによるものです。そこで、 dp配列を1で初期化します。 2つの変数iとjがあります。最初は私は1になり、 jは0になります 。私たちの配列は次のようになります：
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
配列の上の数字は、シーケンスの対応する要素を表します。私たちの戦略は次のとおりです：
if Item[i] > Item[j]
dp[i] := dp[j] + 1
それは私の要素は、jにおける要素よりも大きい場合、我々はそれを私の要素が含まれている場合、Jの要素が含まれているLISの長さは、長さ1だけ増加することを意味します。この例では、 i = 1およびj = 0の場合、 Item [i]はItem [j]よりも大きいです。したがって、 dp [i] = dp [j] + 1 。私たちの配列は次のようになります：
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
各ステップで、我々はiとjのアップを増やすだろうし、その後0にJをリセットし、Iをインクリメントします。今のところ、 jはiに達しているので、 iを2に増やします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 2 、 j = 0の場合、 Item [i]はItem [j]より大きくないので、何もせずにjをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
I = 2、J = 1、 項目について[i]の 項目[j]を超えていないので、我々は何もしないし、jは限界に達しているので、私たちは私をインクリメントし、0にJをリセットします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 3 、 j = 0の場合、 Item [i]はItem [j]より大きくないので、何もせずにjをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 3 、 j = 1の場合、 Item [i]はItem [j]より大きくないので、何もせずにjをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 3 、 j = 2の場合、 Item [i]はItem [j]よりも大きいので、 dp [i] = dp [j] + 1です。その後、 jが限界に達したので、再びjを0にリセットしてiをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 4 、 j = 0の場合、 Item [i]はItem [j]よりも大きいので、 dp [i] = dp [j] + 1です。その後、 jをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 4 、 j = 1の場合、 Item [i]はItem [j]より大きい。 dp [i] = dp [j] + 1が私たちに3を与えることに気付くことができます。これは、 Item [j]の LISを取り、 Item [i]を追加すると、 3、6}より前の3,4,6}そこで、 dp [i] = dp [j] + 1を設定します。次に、 jをインクリメントします。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
i = 4 、 j = 2の場合、 Item [i]はItem [j]より大きい。しかし、この場合、 dp [i] = dp [j] + 1を設定した場合、{-1,6}は2をとります。{3,4,6}はItem [私は] 。だから我々はこれを捨てる。戦略に条件を追加します：
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
jを1ずつ増やします。この戦略に従って、 dp配列を完成させると、次のようになります。
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
次に、この配列を繰り返して、LISの長さになる最大値を見つけます。私たちの疑似コードは次のようになります：
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
このアルゴリズムの時間複雑度はO(n²)ここで、 nはシーケンスの長さです。
元のシーケンスを調べるには、逆方向に繰り返し、長さと一致させる必要があります。手順は次のとおりです。
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
このアルゴリズムの時間複雑度は、 O(n) 。
最長のパリンドロームサブシーケンス
与えられた文字列の中で最長のパリンドロームサブシーケンス（LPS）は何ですか？文字列agbdbaを取ってみましょう。このストリングのLPSは長さ5の abdbaです。覚えておいてください、私たちは部分列を探しているので、文字は元の文字列で連続している必要はありません。配列の最長回文部分文字列は長さ3の bdbです。しかし、ここではその部分列に集中します。この問題を解決するためにダイナミックプログラミングを使用します。
最初は、元のシーケンスと同じ次元の2D配列を取ります。例： S = "agbdba"場合、 dp [6] [6]配列を取る。ここで、 dp [i] [j]は、文字をs [i]からs [j]まで考えると、LPSの長さを表します。例えば。文字列がaa ならば 、 dp [0] [1]は2を格納します。今度は、ストリングの長さを変えて考え、できるだけ長くできる長さを見つけます。
長さ= 1 ：
ここでは、一度に1文字しか検討していません。したがって、長さが1の文字列があれば、LPSは何を持つことができますか？もちろん答えは1です。どのようにそれを格納するには？ dp [i] [j]ここで、 iはjと等しく、長さ1の文字列を表します。したがって、 dp [0] [0] 、 dp [1] [1] 、 dp [2] [2] 、 dp [3] [3] 、 dp [4] [4] 、 dp [ 5] 〜1 。私たちの配列は次のようになります：
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
長さ= 2 ：
今回は長さ2の文字列を考えます。今、長さ2の文字列を考慮すると、LPSの最大長は、文字列の2つの文字が同じである場合に限り、2することができます。だから私たちの戦略は：
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Length = 2の戦略に従って配列を埋めると、次のようになります。
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
長さ= 3 ：
今度は元の文字列を3文字ずつ見ています。今から私たちが作る文字列はLPSによって決定されます：
- 最初の文字と最後の文字が一致する場合、最初と最後の文字を除外すればLPS +を作ることができる項目が少なくとも2つあります。残っている文字列から最高のものを作ることができます。
- 最初と最後の文字が一致しない場合、私たちが作ることができるLPSは、すでに計算した最初の文字または最後の文字を除外したものから来ます。
サマー化するために、
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
我々は長さ = 6までの長さ = 3用のDP配列を記入した場合、我々は得られます。
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
これは我々が必要とするdp配列であり、 dp [0] [5]にはLPSの長さが含まれます。私たちの手順は次のようになります：
Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
dp[i][i] := 1
end for
for i from 0 to (n-2)
if S[i] := S[i+1]
dp[i][i+1] := 2
else
dp[i][i+1] := 1
end if
end for
Length := 3
while Length <= n
for i from 0 to (n - Length)
j := i + Length - 1
if S[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
end for
Length := Length + 1
end while
Return dp[0][n-1]
このアルゴリズムの時間複雑度はO(n²)であり、ここでnは与えられた文字列の長さです。最長回文サブシーケンス問題は、最長共通サブシーケンスに密接に関連しています。 2番目の文字列を最初の文字列の逆にして長さを計算して結果を出力すると、与えられた文字列の最長の回文部分列になります。そのアルゴリズムの複雑さもO(n²)です。