最長共通部分列
部分列 は系列のいくつかの要素を取り出してできた系列のことです。
二つの系列の共通の部分列を 共通部分列 と言います。
共通部分列のうちもっとも長いものを 最長共通部分列 と言います。
最長共通部分列 を求める問題を 動的計画法 を使って解いていきます。
問題
2つの文字列があります。 これら2つの共通部分列の長さの最大値を求めて下さい。
解法・ソースコード
メモ化テーブル を次のように定義します。
memo[i][j] は、【1つめの文字列のi文字まで】と【2つめの文字列のj文字まで】の 最長共通部分列の長さ
この定義を踏まえて、漸化式 を作成し 動的計画法(メモ化テーブル) を実装すると次のようになります。
[Google Colaboratory]
1 | #---------- 入力例 ---------- |
[実行結果]
解: 4
解は 4 となりました。
2つの文字列を確認すると 最長共通部分列 が B, C, B, A となっていて解が正しいことが分かります。