動的計画法を1から解説 — 部分問題を覚えておくということ

素朴な再帰はなぜ指数爆発するのか。メモ化と表埋めで何が変わるのか。フィボナッチ・ナップサック・編集距離を順に分解し、編集距離が音声認識のWERや拡散モデルのステップ選択にそのまま現れることまで見ます。

比喩: 同じ道を何度も測り直していないか

地図のない山で、山頂までの最短時間を知りたいとします。分岐に来るたびに「左の道は山頂まで何分か」「右は何分か」を調べ、短いほうを選ぶ。素直なやり方ですが、山道は途中で合流します。合流点から先の区間を、左ルートを調べるときに1回、右ルートを調べるときにもう1回——まったく同じ区間を何度も測り直しているわけです。

一度測ったら手帳に書いておけばいい。次にその合流点に来たら、測らずに手帳を見る。これが動的計画法（dynamic programming, DP）のすべてです。厳めしい名前がついていますが、中身は部分問題の答えを覚えておく、ただそれだけです。

素朴な再帰は、なぜ指数爆発するのか

フィボナッチ数列で見ます。定義がそのまま再帰の形をしています。

つまり「$n$ 番目の値は、1つ前と2つ前の和」。それ以上の意味はありません。$F$ は「番号を渡すとその値が返ってくる関数」、$n$ は何番目かを表す番号で、$F(0)=0,\ F(1)=1$ は「出発点だけは手で決めておく」という宣言です。そのままコードにすると3行です。

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

正しく動きますが、fib(40) あたりで明確に待たされ、fib(60) は帰ってきません。呼び出しの木を描くと理由が見えます。fib(5) を求める過程で fib(3) は2回、fib(2) は3回、fib(1) は5回呼ばれます。$n$ が1増えるごとに枝の数が黄金比 $\varphi = (1+\sqrt{5})/2 \approx 1.618$ 倍に増えるので、計算量は $O(\varphi^n)$ ——指数関数です（計算量の話の表でいう「論外」の行）。

無駄の正体ははっきりしています。同じ引数の呼び出しが、何度も最初から走り直している。

メモ化: 一度計算したら覚えておく

辞書を1つ用意して、計算済みの答えを入れておくだけです。

def fib(n, memo={}):
    if n < 2: return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

追加したのは3行。それだけで計算量は $O(\varphi^n)$ から $O(n)$ に落ちます。部分問題は $F(0)$ から $F(n)$ までの $n+1$ 個しかなく、それぞれちょうど1回だけ中身が計算されるからです。2回目以降は辞書を引くだけ（平均 $O(1)$ — データ構造の話）。

指数から線形へ。これが「時間をメモリで買う」取引の、最も気持ちのいい例です。この書き方をメモ化（memoization）、またはトップダウンDPと呼びます。

表を埋める: ボトムアップDP

同じことを、再帰を使わずに書けます。小さい部分問題から順に表を埋めていくのです。

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]

計算量はメモ化と同じですが、再帰の深さを気にしなくてよく、定数倍も軽い。そして何より、表を眺めると無駄が見えるのが利点です。この式は直前の2つしか参照していません。ならば配列は要らず、変数2つで足ります——空間が $O(n)$ から $O(1)$ に落ちる。表を埋めてから要らない行を捨てるのは、DPの定石です。