2026-08-05·無料·10分で読めます

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

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

要点

動的計画法（DP）の中身は、部分問題の答えを覚えておくことだけである。
素朴なフィボナッチ再帰の計算量は O(φ^n) だが、メモ化すると O(n) に落ちる。
DPが効く条件は、部分構造最適性と部分問題の重複の2つである。
ナップサック問題のDPは O(nW) で、W は入力の数値なので擬多項式時間と呼ばれる。
編集距離は削除・挿入・置換の3候補の min を表に埋めて求め、計算量は O(mn) である。

出典: NIST Digital Library of Mathematical Functions, §24.15 Related Sequences of Numbers (Fibonacci and Lucas Numbers) · Learning to Efficiently Sample from Diffusion Probabilistic Models

#dynamic-programming #algorithms #edit-distance #knapsack #optimization

対象textタスクalgorithms

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

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

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

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

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

F(n) = F(n-1) + F(n-2), \qquad F(0)=0,\ F(1)=1

(1)

つまり「 $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の定石です。

FIG 1編集距離の表が埋まっていく様子。各マスは「上・左・左上」の3つを見るだけで決まり、右下が答えになる

DPが効く2つの条件

どんな問題でもDPになるわけではありません。必要なのは2つだけです。

部分構造最適性 — 全体の最適解が、部分問題の最適解の組み合わせで作れる
部分問題の重複 — 同じ部分問題が何度も現れる

1つ目が成り立たなければDPは間違った答えを返します。2つ目が無ければ、それは単なる分割統治であって、覚えておく意味がありません。

そして設計の実務は、ほぼ「何を部分問題と呼ぶか」を決めることに尽きます。状態の定義さえ決まれば、漸化式は自然に落ちてきます。

ナップサック問題: 入れるか、入れないか

容量 $W$ のカバンに、重さ $w_i$ ・価値 $v_i$ の品物を詰めて価値の合計を最大にする問題です。全通り試せば $2^n$ 通りあります。

部分問題を「最初の $i$ 個までを考え、容量が $w$ のときの最大価値」と定義し、 $dp[i][w]$ と書きます。

dp[i][w] = \max\big(dp[i-1][w],\ \ dp[i-1][w - w_i] + v_i\big)

(2)

つまり $\max$ は「2つの候補のうち良いほうを採る」、 $w - w_i$ は「その品物の重さのぶんだけカバンを空けておく」ということです。式が言っているのは、結局「 $i$ 番目を入れるか入れないか」の二択だけ。

$i$ 番目の品物についての選択肢は2つしかありません。入れないなら価値は $i-1$ 個までの答えのまま（左側）。入れるなら、その重さ分を空けておいた状態での答えに価値 $v_i$ を足す（右側）。大きいほうを採る、それだけです。

表の大きさは $n \times W$ なので計算量は $O(nW)$ 。 $2^n$ からの劇的な改善ですが、注意点があります。 $W$ は「品物の個数」ではなく「入力に書かれた数値」です。 $W$ が巨大なら表も巨大になる。これを擬多項式時間と呼び、DPの効く範囲を示す言葉として覚えておく価値があります。

編集距離: 文字列をどれだけ直せば一致するか

編集距離（レーベンシュタイン距離）は、文字列 $s$ を $t$ に変えるのに必要な最小の編集回数です。編集は「1文字の置換」「1文字の削除」「1文字の挿入」の3種類。

部分問題は「 $s$ の先頭 $i$ 文字を、 $t$ の先頭 $j$ 文字にする最小手数」、これを $D[i][j]$ と書きます。

D[i][j] = \min\big(D[i-1][j] + 1,\ \ D[i][j-1] + 1,\ \ D[i-1][j-1] + c\big)

(3)

つまり $+1$ は「編集を1回使った」ぶんの加算、 $\min$ は「いちばん安く済む直し方を採る」という意味です。これは「1手前の3つの状態のうち、ここへ最も少ない手数で到達できる道を選ぶ」ということ。

$c$ は、 $s$ の $i$ 文字目と $t$ の $j$ 文字目が同じなら0、違えば1です。3つの候補はそのまま3種類の編集に対応します。1つ目は $s$ 側の1文字を削除して残りを合わせる場合、2つ目は $t$ 側の1文字を挿入する場合、3つ目は置換（文字が一致していればコスト0で斜めに進む）。最小のものを選べば、それがそこまでの最小手数です。

def edit_distance(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i          # s を全部削除する
    for j in range(n + 1): dp[0][j] = j          # t を全部挿入する
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            c = 0 if s[i - 1] == t[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,     # 削除
                           dp[i][j - 1] + 1,     # 挿入
                           dp[i - 1][j - 1] + c) # 置換
    return dp[m][n]

二重ループが表を左上から右下へ埋め、右下のマスが答えです。計算量は $O(mn)$ 。空間も $O(mn)$ ですが、各行は直前の行しか見ていないので、2行だけ持てば $O(n)$ に落ちます。

AIの実装に、この表がそのまま出てくる

編集距離は競技プログラミングの題材ではなく、現役の道具です。

音声認識のWER — 認識精度は単語誤り率で測ります。

$\mathrm{WER} = \frac{S + D + I}{N}$

つまり「間違えた単語の数を、正解文の単語数で割った割合」です。0なら完全一致、値が大きいほど誤りが多い。 $S$ は置換、 $D$ は削除、 $I$ は挿入の回数、 $N$ は正解文の単語数です。そしてこの $S, D, I$ は、単語を1文字と見なして編集距離のDP表を埋め、最適経路を逆にたどって数え上げたものにほかなりません。評価指標の定義そのものが、上の漸化式でできています。要約評価で使われるROUGE-Lの最長共通部分列も、同じ型のDPです。

系列のアライメント — HMMのビタビ復号、CTCの前向き計算、音声のDTW（動的時間伸縮）。どれも「時刻 $t$ で状態 $s$ にいるときの最良値」を表に持ち、隣のマスから遷移してくる構造で、編集距離と骨格が同じです。

拡散モデルのステップ選択 — サンプリングの手数を減らしたいとき、目的が各ステップの寄与の和に分解できるなら、「どの時刻を残すか」は全探索ではなくDPで最適に選べます。実際にこの形の手法が提案されています。残す・残さないを順に決めていく構造がナップサックとまったく同じだと気づけば、道具はすでに手元にあるわけです。

行列積の掛ける順序 — 複数の行列を掛け合わせるとき、結合の順序で総演算数は大きく変わります。最適な括弧の付け方を求めるのも古典的なDPで、これは次の記事の話につながります。

実務で効く4つ

1. まず素朴な再帰を書く 正しい再帰さえ書ければ、メモ化は辞書を1つ足すだけです。いきなり表を設計しようとすると、たいてい漸化式を間違えます。

2. 状態の意味を一文で書き残す $dp[i][j]$ が何を表すのかを、コメントに日本語の文で書く。DPのバグの大半は、この定義が実装の途中でぶれることから生まれます。

3. 境界を先に埋める $D[i][0]$ や $D[0][j]$ のような端の行・列は、漸化式ではなく問題の意味から決まります。ここを確定させてから中身のループに入ります。

4. 表の依存を見てから空間を削る 直前の1〜2行しか参照していないなら、 $O(mn)$ の表は不要です。ただし「どう編集したか」の経路復元が必要なら表は捨てられません。ここも時間と空間の取引です。

まとめ

DPの正体は「部分問題の答えを覚えておく」だけ。素朴な再帰の $O(\varphi^n)$ が $O(n)$ になる
使える条件は2つ、部分構造最適性と部分問題の重複。設計の本体は状態の定義
ナップサックは $O(nW)$ の擬多項式時間。 $W$ は個数ではなく数値なので、大きいと効かない
編集距離は削除・挿入・置換の3候補の $\min$ を表に埋めるだけ。 $O(mn)$ 、空間は2行で足りる
WER、ビタビ、CTC、DTW、拡散のステップ選択——AIの現場に同じ表が繰り返し現れる

次は、AIの計算時間のほとんどを占める演算——行列積のコストを分解します（行列積のコスト）。