同じ計算を何度もしていない？｜動的計画法・再帰・最長共通部分列

再帰を使えば、問題を小さく分けられます。それでも処理が遅いのはなぜでしょうか。同じ小問題を何度も解いている場合があります。計算結果を再利用する前に、何を同じ問題とみなすかを決めましょう。

事例：二つの操作履歴の共通部分を探す

操作履歴AはABC、BはBACです。順序を保ち、一部の文字を取り除いてできる列のうち、両方に共通する最長のものを探します。連続して並ぶ必要はありません。

ACとBCはどちらも長さ2の答えです。ABはAにはありますが、BではAより先にBが現れるので共通の部分列になりません。長さを求める問題と、列そのものを求める問題を分けます。

表の一マスは、何を表す？

D[i][j]を「Aの先頭i文字とBの先頭j文字の最長共通部分列の長さ」と定めます。iとjは文字そのものの添字ではなく、使用する文字数です。A[i-1]が先頭i文字の最後になります。

1. 状態

   小問題を識別する情報。ここでは、二つの履歴をそれぞれ何文字まで使うかです。

2. 値

   その状態で求める答え。ここでは最長共通部分列の長さです。

3. 初期値

   片方が空なら共通する文字もないため、D[0][j]とD[i][0]は0です。

表の大きさは(m+1)行×(n+1)列です。0文字を表す行と列を忘れると、最初の文字を処理する際に表の外を参照します。状態の説明ができると、必要な領域も決まります。

最後の文字が一致したら、どこを使う？

A[i-1]とB[j-1]が同じなら、それらを共通列の最後に使えるのでD[i-1][j-1]+1とします。違うなら、A側かB側の最後を使わない二つの候補を比べます。

一致：D[i][j] = D[i-1][j-1] + 1
不一致：D[i][j] = max(D[i-1][j], D[i][j-1])

不一致で上と左を足すと、同じ文字や重複する小問題を二度数えてしまいます。ここで選ぶのは、共通列の長さが大きい方です。最短経路や個数を数える別の問題では、式をそのまま流用できません。

どの順序で表を埋めればよい？

iを1から増やし、その行のjも1から増やします。すると上の行と左のマスは計算済みです。式の依存先が先に求まる順序で更新することが、表を正しく使う条件です。

右下のD[3][3]は2です。一致したCを足す直前のD[2][2]は1でした。不一致のD[2][2]では上と左がともに1なので、長さだけならどちらを選んでも結果は変わりません。

再帰とメモ化でも、同じ答えになる？

再帰は、関数が自分を呼び出して小問題を解く方法です。動的計画法では、重複する小問題の結果を保存して再利用します。再帰を使うことと、動的計画法を使うことは同じ意味ではありません。

トップダウンでは必要な状態を再帰で求め、計算済みなら保存した値を返します。ボトムアップでは初期値から順に表を埋めます。どちらも同じ状態と式を使えば同じ長さを求められます。

メモに0が入っていても、未計算とは限りません。答えが0になる状態もあります。未計算を別の値やフラグで区別し、保存するキーにiとjの両方を含めます。

短いコードで、表の動きを確かめる

def lcs_table(a, b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1] + 1
            else:
                d[i][j] = max(d[i - 1][j], d[i][j - 1])
    return d

長さだけを返すなら、戻り値の最後の行・最後の列を取り出します。表を二行に減らすと追加領域をO(n)にできますが、過去のマスを使う通常の復元には別の工夫が必要です。

長さ2から、ACを復元するには？

右下から戻り、文字が一致したらその文字を記録して左上へ進みます。不一致なら値の大きい上か左へ進みます。同値では、例えば上を選ぶ規則に固定します。

この規則ではCを記録し、同値のマスから上へ進んでAを記録します。記録順はCAなので、最後に逆順にしてACを得ます。同値で左を選ぶと別の正しい列になる場合があります。

各マスを一定時間で求めるこの実装の時間はO(mn)、表の領域もO(mn)です。単位時間あたりの実行速度や実データの長さがなければ、秒数は決められません。

演習1：状態の意味

条件：D[i][j]は先頭i文字と先頭j文字のLCS長です。

問い：D[2][1]は何を比較した値ですか。

解答例：ABとBの最長共通部分列の長さ1です。

根拠：iとjを文字数として、Aの先頭2文字、Bの先頭1文字を切り出します。

誤答の理由：A[2]とB[1]の一文字だけを比べると、状態の意味と添字を混同します。

演習2：不一致の式

条件：D[1][2]=1、D[2][1]=1で、Aの2文字目はB、Bの2文字目はAです。

問い：D[2][2]を求めてください。

解答例：max(1,1)=1です。

根拠：最後の文字が違うため、一方の最後を使わない候補を比較します。

誤答の理由：1+1=2は二つの候補を結合してしまい、順序を満たす共通列を示せません。

演習3：境界と領域

条件：Aは長さ3、Bは長さ3です。

問い：0文字の行と列を含む表は何マスですか。

解答例：4×4=16マスです。

根拠：添字は両方とも0から3まであり、空の接頭部分も状態に含めます。

誤答の理由：3×3では初期値を格納する行と列が不足します。

演習4：更新順

条件：D[i][j]は上・左・左上を参照します。

問い：行ごとに更新するなら、iとjをどちら向きに進めますか。

解答例：iもjも小さい方から大きい方へ進めます。

根拠：依存先の行や同じ行の左を先に計算する必要があります。

誤答の理由：右下から左上へ埋めると、この接頭部分を使う式では未計算の値を参照します。

演習5：メモ化の条件

条件：未計算を0とし、0以外だけを保存済みと判定します。

問い：どのような問題がありますか。

解答例：正しい答えが0の状態を未計算と誤認し、再計算してしまいます。

根拠：共通文字がない小問題の答えは0になり得ます。

誤答の理由：結果が0なら保存不要という判断では、計算結果の再利用を十分にできません。

演習6：答えの復元

条件：表の右下は2で、復元時にC、次にAを記録しました。

問い：返す列と、長さだけの二行表で注意する点を答えてください。

解答例：記録を逆順にしてACを返します。二行表だけでは通常の復元で使う過去の値を失います。

根拠：復元は末尾から進み、上や左の過去のマスを参照します。

誤答の理由：CAを返すと元の二つの履歴の順序を保てません。領域削減と復元を同一視しません。

出典と仕様を確認する

IPA：APシラバス Ver.7.2

MIT 6.006：動的計画法の状態と依存関係

MIT 6.046J：最長共通部分列

関連テーマを続けて学ぶ

配列と処理のトレース

探索とデータ構造