動的計画法（DP）とは？仕組み・コード・例題をわかりやすく解説

動的計画法が解く問題

多くの問題は、最良、最安、または場合の数を求めます。ある金額を作る最少のコイン枚数、2つの文字列の最長共通部分列、袋に入る最も価値の高い品物の組、グリッドを通る経路の数、などです。素朴な再帰による解法は、同じ小さなケースを指数的な回数も再計算することがよくあります。DPはその繰り返しをなくします。

名前の由来は、1950年代にこの手法を開発したリチャード・ベルマン（Richard Bellman）です。ここでの「プログラミング」は、計画を立てること、または表を埋めることを指し、コードを書くことではありません。

考え方を言葉で説明すると

素朴な再帰によるフィボナッチ数の計算が、問題点をよく表しています。fib(5) は fib(4) と fib(3) を呼び、fib(4) はまた fib(3) を呼び、と続いて、呼び出しの回数が指数的に増えます。各結果を初めて計算したときに保存しておけば、以降の呼び出しは即座に終わります。

1. 状態を定義します。部分問題はどのような形をしているか。たとえば、best[a] = 金額 a を作る最少のコイン枚数。
2. 漸化式を書きます。状態は、より小さな状態からどう計算されるか。best[a] = 1 + min(best[a - c] for each coin c)。
3. 基底ケースを決めます。best[0] = 0。
4. 順序を決めます。メモ化によるトップダウンか、小さな状態が必ず先に埋まるボトムアップか。
5. 適切な状態から答えを読み取り、必要なら実際の選択を復元します。

トップダウン：functoolsによるメモ化

Pythonでは、functools.cache（Python 3.9以降）または functools.lru_cache で、1行で関数にメモ化を追加できます。

from functools import cache

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

print(fib(80))  # 23416728348467685

デコレータがなければ、fib(80) は 10¹⁶ 回を超える再帰呼び出しを行います。デコレータがあれば、0 から 80 までの各値は1回だけ計算されます。

例題：ボトムアップによるコイン問題

コインは 1、3、4、金額は 6 です。貪欲法ではまず 4 を取り、4 + 1 + 1 で3枚必要ですが、3 + 3 なら2枚で済みます。DPは、a = 0 から 6 まで best[a] を埋めることで、真の最小値を見つけます。

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

二次元の例：最長共通部分列

2つの系列に対する多くのDP問題は、グリッドを使います。dp[i][j] は、一方の文字列の最初の i 文字と、もう一方の最初の j 文字に対する答えです。最長共通部分列（LCS）では、文字が一致すれば対角線方向に延ばし、そうでなければどちらかの文字列から1文字を除いた場合のうち良いほうを取ります。

def lcs(a, b):
    dp = [[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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

長さ4のLCSの1つは BCBA です。同じ表の構造で編集距離も解けます。diffツールが2つの文字列がどれだけ異なるかを測るのは、この方法です。

時間計算量と空間計算量

一般的な規則は、時間 = 状態の数 × 状態ごとの作業量、空間 = 保存する状態の数、です。

ナップサック問題の O(n × W) は擬多項式時間です。入力のビット数ではなく数値 W そのものに依存するため、W が非常に大きいと遅くなります。

よくある間違いとDPを使う場面

• 状態の誤り：漸化式が、状態に含まれていない情報（たとえば、どの品物がすでに使われたか）を必要とする場合、答えが間違います。その情報を状態に加えてください。
• 埋める順序の誤り：ボトムアップのループは、状態が読み取られる前に、その状態を必ず計算していなければなりません。
• テーブルサイズの1つのずれ：長さ n の文字列では、空の接頭辞を含めるために n + 1 行が必要です。
• 再帰が深すぎる：10,000個の状態に対するメモ化再帰は、Pythonの再帰上限を超えることがあります。ボトムアップに切り替えてください。
• ハッシュできない引数：functools.cache にはハッシュ可能な引数が必要なので、リストの代わりにタプルを渡してください。

面接や実務での典型的な用途：階段の上り方、House Robber、最長増加部分列、単語分割、グリッドの経路数、編集距離、ナップサック問題、連鎖行列積。実務では、バイオインフォマティクスの配列アラインメント、diffツール、スペルチェッカー、音声認識（ビタビアルゴリズム）、ベルマン–フォード法などの最短経路があります。