動的計画法の原理（最適部分構造と重複部分問題）

DP が成立する2つの条件

動的計画法（DP）は「部分問題の答えを使い回して、指数的な重複計算を消す」設計技法です。ただし、どんな問題にも効くわけではありません。次の2条件が揃ったときに初めて成立します。

最適部分構造は正しさの条件、重複部分問題は**速さ（効かせる意味があるか）**の条件です。最適部分構造が無ければ DP で正解にたどり着けず、重複が無ければ DP にしても素朴な分割統治と計算量が変わりません。両方を満たして初めて「正しく、かつ速い」DP になります。

なぜ素朴な再帰は遅いのか

重複部分問題を体感する典型がフィボナッチです。素朴な再帰は同じ値を何度も計算し、呼び出し回数が O(2ⁿ) に膨らみます。

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) の呼び出し木には fib(3) が2回、fib(2) が3回現れます。異なる引数の値は n+1 通りしかないのに、木は指数的に広がる。つまり「本質的な部分問題はたかだか n 種類」なのに、それを何度も再計算しているのが遅さの正体です。計算量の見積もりに不安があれば計算量と Big-O 記法を先に押さえてください。

DP の発想は単純で、各部分問題を一度だけ解いて結果を保存し、2回目以降は読み出す。これで呼び出し回数が「部分問題の種類数」に上限が定まり、O(n) に落ちます。

メモ化とボトムアップは等価

DP の実装は大きく2系統あり、計算する部分問題の集合が同じなら両者は等価です。

# メモ化：再帰の形を保ったまま辞書にキャッシュ
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# ボトムアップ：依存が先に埋まる順序でループ
def fib(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 依存はすべて既に確定済み
    return dp[n]

両者の計算量は同じ O(n) です。違いは順序の決め方だけ。メモ化は「必要になった瞬間に計算する」遅延戦略で、ボトムアップは「依存が先に並ぶよう手で整列する」前倒し戦略です。ボトムアップが成立するには、部分問題の依存関係に循環が無い（有向非巡回＝トポロジカル順序が引ける）ことが前提になります。

状態設計と遷移の立て方

DP 設計の核心は2つを決めることに尽きます。

• 状態：部分問題を一意に識別する引数の組。ここでは dp[...] の添字に相当する。
• 遷移：ある状態の答えを、より小さい状態の答えから導く漸化式。再帰関数の本体に相当する。

計算量は機械的に決まります。状態数 × 1遷移あたりのコストです。状態を (i, j) の2次元で取り、各遷移が定数本の参照で済むなら、状態数ぶんのセルを定数時間で埋めて全体が状態数オーダーになります。設計とは「正しい遷移が引ける最小の状態」を見つける作業だと言えます。

例1：0-1 ナップサック

容量 W のナップサックに、重さ w[i]・価値 v[i] の品物 n 個から選んで価値を最大化します。各品物は入れるか入れないかの二択（0-1）です。素朴な全探索は 2ⁿ 通りですが、状態をうまく取ると多項式時間になります。

• 状態 dp[i][c]：先頭 i 個まで見て、容量 c をちょうど上限としたときの最大価値。
• 遷移：品物 i を「入れない」か「入れる」かで場合分けする。

dp[i][c] = max(
  dp[i-1][c],                            # i を入れない
  dp[i-1][c - w[i]] + v[i]   (c >= w[i]) # i を入れる
)

状態数は n × W、遷移は定数本の参照なので、全体は O(nW)。ここで重要なのは、これは入力サイズ（n と W のビット長）に対しては多項式ではなく、W の値に比例する擬多項式だという点です。W が桁数に対して指数的に大きいと現実的に解けません。実際 0-1 ナップサックは NP 困難で、DP で多項式風に見えるのはこの擬多項式のからくりによります。計算困難性の枠組みは計算複雑性クラス P と NPを参照してください。

例2：編集距離（レーベンシュタイン距離）

文字列 A（長さ n）を B（長さ m）に変換する最小操作回数を求めます。操作は1文字の挿入・削除・置換の3種類です。

• 状態 dp[i][j]：A の先頭 i 文字を B の先頭 j 文字に変換する最小コスト。
• 遷移：末尾1文字をどう処理するかで3つの手から最小を取る。

dp[i][j] =
  dp[i-1][j-1]                 if A[i] == B[j]   # 一致、操作不要
  else 1 + min(
    dp[i-1][j],                # A の末尾を削除
    dp[i][j-1],                # B の末尾を挿入
    dp[i-1][j-1]               # 末尾を置換
  )
# 境界: dp[i][0] = i, dp[0][j] = j（空文字列との距離）

末尾の文字が一致するなら操作は要らず、その手前の部分問題 dp[i-1][j-1] に帰着します。これが最適部分構造そのものです。状態数 n × m、各遷移は3つの参照の最小なので O(nm)。dp[i][*] は1つ前の行 dp[i-1][*] しか参照しないため、表を2行ぶんだけ持てば空間 O(min(n, m)) に削減できます。

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i           # a の先頭 i 文字を空文字へ＝i 回削除
    for j in range(m + 1):
        dp[0][j] = j           # 空文字を b の先頭 j 文字へ＝j 回挿入
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[n][m]

設計時のチェックリスト

DP を当てる前に、次を順に確認すると外しにくくなります。

• 最適部分構造はあるか：全体の最適解が部分問題の最適解から構成できることを言葉で説明できるか。説明できないなら遷移は書けない。
• 状態は十分か・最小か：未来の判断に必要な情報を漏れなく、かつ余計なく持っているか。状態数が計算量を直接決める。
• 遷移に循環は無いか：依存が有向非巡回でないと、ボトムアップの順序が引けない（メモ化でも無限ループになる）。
• 計算量は許容範囲か：状態数 × 1遷移コストを概算する。擬多項式（値に依存）になっていないかを特に疑う。

DP は「賢い再帰」ではなく、重複する部分問題の集合を一度ずつ解き切るための整理術です。状態を引数の組、遷移を漸化式と見抜ければ、メモ化とボトムアップは同じ計算を別の順序で回しているだけだとわかります。難所は実装ではなく、正しい状態と遷移を立てる設計のほうにあります。