動的計画法（DP）入門 - メモ化とテーブル化で解く定番アルゴリズム

「小さな問題の答えを覚えておいて、大きな問題に使い回す」——たったこれだけの発想で、指数時間かかっていた計算が一瞬で終わることがあります。それが動的計画法（Dynamic Programming, DP）です。名前は少しいかめしいですが、やっていることは「同じ計算を何度もしない」という素朴な工夫にすぎません。この記事では、DPが成り立つ2つの条件から始めて、メモ化とテーブル化という2つの実装スタイル、そしてフィボナッチ・コイン問題・0-1ナップサック・編集距離という定番例題を、Pythonの動くコードと計算量つきで整理します。同じ入門シリーズのソートアルゴリズム入門やグラフ探索アルゴリズム入門と合わせて読むと、アルゴリズムの引き出しが一気に増えます。

動的計画法（DP）とは — 成り立つための2条件

DPは、あらゆる問題に効くわけではありません。次の2つの条件を満たす問題でこそ威力を発揮します。

• 部分問題の重なり（overlapping subproblems）: 大きな問題を解く過程で、まったく同じ小さな問題が何度も現れる。フィボナッチ数の計算で fib(3) が何度も再計算されるのが典型です。この「重複」を1回だけ計算して覚えておくのがDPの肝です
• 最適部分構造（optimal substructure）: 大きな問題の最適解が、部分問題の最適解を組み合わせて作れる。たとえば「金額100円を最小枚数で作る」答えは、「99円」「98円」などより小さい金額の最小枚数から導けます

逆に言えば、部分問題が重ならないなら覚えておく意味はなく（それは単なる分割統治です）、部分問題の最適解が全体の最適解につながらないなら、DPの遷移式そのものが立ちません。DPを使う前に、まずこの2条件を満たすかを確認するのが出発点になります。

素朴な再帰はなぜ遅いのか — フィボナッチで体感する

フィボナッチ数列 0, 1, 1, 2, 3, 5, 8, ... は fib(n) = fib(n-1) + fib(n-2) で定義されます。素直に再帰で書くと次のようになります。

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

これは正しく動きますが、恐ろしく遅いです。fib(5) を計算するとき、内部で fib(3) が2回、fib(2) が3回…と、同じ計算が爆発的に繰り返されます。呼び出し回数はおよそ 2 * fib(n+1) - 1 回で、これは O(φ^n) の指数時間です（φ は黄金比でおよそ 1.618。ゆるく O(2^n) オーダーと表現されることもあります）。n が50を超えたあたりで、素朴な再帰は現実的な時間で終わらなくなります。

原因は明確で、同じ部分問題を何度も計算し直しているからです。まさに「部分問題の重なり」があるのに、それを活用していない状態です。計算量の記法そのものに不安がある方は、先に計算量とBig-O記法 入門を読むと、以降の O(n) や O(2^n) の比較がすっと入ってきます。

メモ化とテーブル化 — 2つの実装スタイル

DPには実装の方向が2つあります。上から降りてくるメモ化（トップダウン）と、下から積み上げるテーブル化（ボトムアップ）です。どちらも「一度計算した部分問題の答えを保存して使い回す」点は同じで、計算量も同じになります。

メモ化（トップダウン）

素朴な再帰に「一度計算した答えを辞書に覚えておく」処理を足すだけです。

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:
        return memo[n]          # 計算済みなら即返す
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
 
print(fib_memo(10))   # 55
print(fib_memo(50))   # 12586269025

各 fib(k) は一度だけ計算され、以降は辞書から一定時間で取り出されます。これで計算量は指数時間から O(n) に激減します。ここで答えを覚える辞書は内部的にハッシュテーブルで、平均一定時間の読み書きに支えられています（仕組みはハッシュテーブル入門を参照）。メモ化は「素朴な再帰にキャッシュを足す」だけなので、再帰で問題を素直に書ける人にとって最初の一歩として書きやすいのが利点です。

テーブル化（ボトムアップ）

小さい部分問題から順に配列（テーブル）を埋めていく方式です。再帰を使わないため、関数呼び出しのオーバーヘッドやスタック上限の心配がありません。

def fib_table(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 小さい方から確定させる
    return dp[n]
 
print(fib_table(10))   # 55

dp[i] に「i 番目のフィボナッチ数」という意味を持たせ、i の小さい順に埋めていきます。計算量は O(n)、配列のぶん空間も O(n) です。トップダウンとボトムアップの使い分けは次のように考えると迷いません。

配列の1次元圧縮で空間を削る

フィボナッチでは、dp[i] を求めるのに直前の2つ dp[i-1] と dp[i-2] しか要りません。つまり配列全体を持たず、変数2つで十分です。

def fib_fast(n):
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr   # 直前2つだけ持ち回す
    return curr
 
print(fib_fast(10))   # 55

これで空間は O(n) から O(1) になります。「遷移で参照するのは直近の数マスだけ」という状況では、この次元圧縮が定番のテクニックです。後述のナップサックでも同じ発想が効きます。

DPの設計手順 — 5ステップ

DPは、次の5ステップに沿って考えると立式しやすくなります。慣れないうちは、この順番を紙に書き出すのがおすすめです。

1. 状態（state）を定義する: 「何が決まれば部分問題が一意に定まるか」を決め、dp[...] が表す意味を日本語で言い切る（例: dp[x] は金額 x を作る最小枚数）
2. 遷移（transition）を立てる: ある状態の答えを、より小さい状態の答えからどう作るかを式にする
3. 初期値（base case）を決める: 遷移の起点になる自明な値を埋める（例: dp[0] = 0）
4. 計算順序を決める: 参照する側が先に確定しているように順番を定める（ボトムアップなら小さい状態から）
5. 答えの取り出し方を決める: 最終的に読むべきマスを決める（例: dp[amount]）

このうち最重要なのは1の状態の定義です。状態さえ的確に決まれば、遷移式は自然と見えてきます。以降の例題も、すべてこの5ステップで読み解いていきます。

例題1: コイン問題（最小枚数と組み合わせ数）

コイン問題は「決まった額面のコインで、ある金額をどう作るか」を問う定番です。まずは最小枚数を求めます。状態は dp[x] =「金額 x を作る最小枚数」、遷移は「使うコイン1枚を選び、残額の最小枚数に1を足したものの最小」です。

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount        # dp[x] = 金額 x を作る最小枚数
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[amount] if dp[amount] != INF else -1
 
print(min_coins([1, 3, 4], 6))   # 2  （3 + 3 の2枚が最小）

額面 [1, 3, 4] で6円を作ると、dp は [0, 1, 2, 1, 1, 2, 2] と埋まり、答えは dp[6] = 2 です。貪欲に「大きいコインから使う」と 4 + 1 + 1 の3枚になってしまいますが、DPは全パターンを暗黙に調べるので 3 + 3 の2枚を正しく見つけます。時間計算量は金額を A、コイン種類数を K として O(A * K)、空間は O(A) です。

次に組み合わせ数（何通りの作り方があるか、順序は区別しない）を求めます。ループの入れ子の順序が最小枚数版と違う点に注意してください。

def count_combinations(coins, amount):
    dp = [1] + [0] * amount     # dp[0] = 1（何も選ばない1通り）
    for c in coins:             # コインを外側にするのが肝
        for x in range(c, amount + 1):
            dp[x] += dp[x - c]
    return dp[amount]
 
print(count_combinations([1, 2, 5], 5))   # 4

[1, 2, 5] で5円を作る組み合わせは 5 / 2+2+1 / 2+1+1+1 / 1+1+1+1+1 の4通りです。

例題2: 0-1ナップサック問題

0-1ナップサック問題は「重さの上限が決まった袋に、価値の合計が最大になるように品物を詰める」問題です。各品物は入れるか入れないかの2択（0か1）で、同じ品物を2個は入れられません。状態は dp[i][c] =「先頭から i 個目までの品物を対象に、容量 c の袋で得られる最大価値」とします。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]              # i 番目を入れない
            if w <= c:
                take = dp[i - 1][c - w] + v      # i 番目を入れる
                if take > dp[i][c]:
                    dp[i][c] = take
    return dp[n][capacity]
 
weights = [2, 1, 3, 2]
values  = [3, 2, 4, 2]
print(knapsack(weights, values, 5))   # 7

遷移は「i 番目を入れない場合（dp[i-1][c]）」と「入れる場合（dp[i-1][c-w] + v）」の大きい方を採るだけです。上の例では容量5の袋に価値の合計7を詰められます。時間計算量は品物数 n、容量 W として O(n * W)、空間も O(n * W) です。

このナップサックも、遷移で参照するのが「1つ前の行」だけなので1次元に圧縮できます。ただし更新を容量の大きい方から行うのが必須です。小さい方から回すと、同じ品物を二重に使ってしまいます。

def knapsack_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):    # 逆順に更新するのが肝
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
    return dp[capacity]
 
print(knapsack_1d([2, 1, 3, 2], [3, 2, 4, 2], 5))   # 7

例題3: 編集距離（レーベンシュタイン距離）

編集距離は「文字列 a を b に変えるのに必要な、1文字の挿入・削除・置換の最小回数」です。スペルチェッカーやDNA配列の比較、差分表示など応用が広い2次元DPの代表例です。状態は dp[i][j] =「a の先頭 i 文字と b の先頭 j 文字の編集距離」とします。

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i          # a の i 文字をすべて削除
    for j in range(n + 1):
        dp[0][j] = j          # b の j 文字をすべて挿入
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]
 
print(edit_distance("kitten", "sitting"))   # 3

kitten を sitting にするには、k を s に置換、e を i に置換、末尾に g を挿入で3回。DPはこれを正しく 3 と算出します。時間計算量は文字列長を m, n として O(m * n)、空間も O(m * n) ですが、参照するのは「1つ前の行」だけなので、フィボナッチと同じ発想で O(min(m, n)) まで圧縮できます。同様の2次元DPに最長共通部分列（LCS）があり、こちらは差分（diff）ツールの中核として使われています。

計算量まとめ（比較表）

ここまでの例題を、状態の意味と計算量つきで一覧にします。

同じ問題でも、素朴な再帰の O(φ^n) とDPの O(n) では、n = 60 あたりで実行時間に天文学的な差が生まれます。DPの価値は、この「指数から多項式への引き下げ」に集約されます。

つまづきやすいポイントと実務での勘所

DPを書くときに詰まりやすい点を挙げておきます。

• 状態の定義が曖昧: dp[...] の意味を一言で言い切れないと、遷移式は絶対に立ちません。まず日本語で「dp[x] は◯◯」と書き切ることが最優先です
• 計算順序の誤り: 参照するマスがまだ埋まっていないと壊れます。メモ化なら再帰が自動で順序を守ってくれますが、テーブル化では自分でループの向きを設計します。ナップサックの1次元版で逆順に回すのはこのためです
• 初期値と境界の抜け: dp[0] や添字が範囲外にならないかは、小さな入力で1回手でトレースして確かめます
• そもそもDP向きか: 2条件（重なり・最適部分構造）を満たさない問題に無理やりDPを当てても遠回りになります

メモ化再帰は、見方を変えると「部分問題どうしの依存関係を表すDAG（有向非巡回グラフ）を、深さ優先で1回だけ訪問している」処理でもあります。DPとグラフ探索が地続きだと分かると理解が深まるので、グラフ探索アルゴリズム入門も合わせて読んでみてください。腰を据えて体系的に学びたくなったら、プログラマーにおすすめの技術書で紹介している定番書が手引きになります。

まとめ

• DPは部分問題の重なりと最適部分構造の2条件を満たす問題で、「同じ計算を1回だけ」にして指数時間を多項式時間へ引き下げる技法
• 実装はメモ化（トップダウン）とテーブル化（ボトムアップ）の2スタイル。計算量は同じで、書きやすさとスタック上限で使い分ける
• フィボナッチは素朴な再帰の O(φ^n) がDPで O(n) に、さらに次元圧縮で空間 O(1) まで削れる
• コイン問題・0-1ナップサック・編集距離は、いずれも状態を定義して遷移を立てるという同じ型で解ける
• 設計は「状態 -> 遷移 -> 初期値 -> 計算順序 -> 答えの取り出し」の5ステップ。中でも状態の定義が最重要

最初のうちは、まず dp[...] の意味を日本語で言い切ることだけを目標にしてみてください。状態さえ定まれば、DPは驚くほど機械的に組み上がっていきます。

参考リンク

• Dynamic programming - Wikipedia
• Knapsack problem - Wikipedia
• Levenshtein distance - Wikipedia
• Longest common subsequence - Wikipedia