白駿9251号LCS

白俊9251号です.
LCS
ダイナミックプログラミングでは,1次元dp配列を用いて多くの問題を解決した.
この問題は基本的に二次元dp配列によって解決される.
しかし,積算1次元dp配列を用いることは2次元を用いるよりも簡単である.

共通部分の数列を決定するには、2つの文字列を順に参照します.
各要素を比較します.
ACAYKP CAPCAK例

A、C比較(AはACAYKPの最初の要素CはCAPCAKの最初の要素)

A、A比較

A,P比較

A,C比較

A、A比較

A、K比較
....

リストとして表示すると、
A CAPCAK => [0 1 0 0 1 0]
そしてACAYKPのCと比較します.
このとき、CAPCAKの2番目のCの前にAが先に出ているので、2番目のCに比べて、これを事前に教えておきます.
コードで表示します.

if cnt < dp[j]:
	cnt = dp[j]

このコードを使用すると、現在チェックされているインデックスの前に
現在のインデックスのdpリストに予め挿入します.
ここで比較演算を行う理由は,我々が最も長いLCSを得るためである.
これは、重複する部分数列により長い数列を追加するためです.
その後同じアルファベットが表示されると、dp値がcntに加算されます.
最後に、dpリストに保存された値の中で最大の値が最も長いLCS長となる.