動的計画法 — DP とメモ化
このトピックを修了すると
動的計画法が必要な状況を判断でき、トップダウン（メモ化）とボトムアップ（タブラ化）の2つの方法で問題を解決できるようになります。
同じ計算を繰り返す問題
フィボナッチ数列を再帰的に実装すると：
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
print(fib(35)) # 9227465 — 約4秒print(fib(50)) # ... 終わらないfib(5)を計算する際に、fib(3)が2回、fib(2)が3回呼び出されます。fib(50)の場合、重複呼び出しは数十億回にもなります。
fib(5)
├── fib(4)
│ ├── fib(3) ← ここでも計算
│ │ ├── fib(2)
│ │ └── fib(1)
│ └── fib(2) ← また計算
└── fib(3) ← また計算
├── fib(2) ← また計算
└── fib(1)時間計算量：O(2^n)。すでに計算した答えを記憶すれば、この問題は解決されます。
動的計画法の条件
DPを適用するには、次の2つが必要です。
1. 重複部分問題（Overlapping Subproblems）
同じ小さな問題が何度も繰り返されます。フィボナッチのfib(3)のように。
2. 最適部分構造（Optimal Substructure）
大きな問題の最適解が、小さな問題の最適解で構成されます。fib(n) = fib(n-1) + fib(n-2)のように。
これら両方を満たせばDPを適用できます。どちらか一方でも満たされない場合は、他の方法（貪欲法、分割統治など）を使用する必要があります。
トップダウン — メモ化
「上から下へ」再帰を維持しつつ、計算結果を辞書（または配列）に保存します。
def fib(n, memo={}): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n]
print(fib(50)) # 12586269025 — 瞬時に完了print(fib(100)) # 354224848179261915075fib(50)が4秒から瞬時に変わります。各fib(k)を1回だけ計算するため、時間計算量はO(n)です。
Pythonでは、functools.lru_cacheを使って、よりきれいに記述できます。
from functools import lru_cache
@lru_cache(maxsize=None)def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)デコレータ1行でメモ化が完了します。
ボトムアップ — タブラ化
「下から上へ」小さな問題から順番に解いていきます。
def fib(n): if n <= 1: 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]再帰を全く使用しないため、スタックオーバーフローのリスクはありません。fib(10000)も問題ありません。
空間の最適化：フィボナッチでは、直前の2つの値があれば十分なので：
def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return bO(n)時間、O(1)空間。
トップダウン vs ボトムアップ
| トップダウン（メモ化） | ボトムアップ（タブラ化） | |
|---|---|---|
| 方式 | 再帰 + キャッシュ | 繰り返し + テーブル |
| 実装 | 元の再帰にキャッシュを追加 | 点火式を繰り返しに変換 |
| 必要な部分だけ計算 | ✅ | ❌（すべて埋める） |
| スタックオーバーフロー | 可能性あり（nが大きい場合） | なし |
| 空間の最適化 | 難しい | 容易 |
一般的に、ボトムアップの方がわずかに高速です（関数呼び出しのオーバーヘッドがない）。また、空間の最適化も容易です。ただし、点を繰り返しに変換するのが直感的でない場合もあるため、状況に応じて選択します。
代表的な問題：階段を上る
階段がn個あり、1段または2段ずつ上ることができます。頂上まで行く方法はいくつありますか？
def climb_stairs(n): if n <= 2: return n dp = [0] * (n + 1) dp[1] = 1 # 1段：1通り dp[2] = 2 # 2段：1+1または2、2通り for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
print(climb_stairs(5)) # 8print(climb_stairs(10)) # 89i番目の段に到達するには、(i-1)から1段上るか、(i-2)から2段上るかのどちらかです。dp[i] = dp[i-1] + dp[i-2] — フィボナッチと同じ構造です。
代表的な問題：0-1ナップサック
ナップサックの容量W、アイテムn個。各アイテムは入れるか入れないかのいずれか（0-1）。価値の合計を最大化します。
def knapsack(W, items): n = len(items) dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1): weight, value = items[i - 1] for w in range(W + 1): dp[i][w] = dp[i - 1][w] # 入れない場合 if w >= weight: dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
return dp[n][W]
items = [(2, 3), (3, 4), (4, 5), (5, 6)] # (重さ、価値)print(knapsack(8, items)) # 10dp[i][w]は、「最初のi個のアイテムで容量wを満たす場合の最大の価値」です。各アイテムについて、「入れる」または「入れない」の2つの選択肢の中で最大の値を記録します。
DP問題の解法パターン
- 状態の定義:
dp[i]が何を意味するかを明確にする - 漸化式の導出:
dp[i]を以前の状態から表現する - 初期値の設定: 最小の問題の答えを埋める
- 順序の決定: どのような順序でテーブルを埋めるかを決定する
- 結果の抽出:
dp[n]またはmax(dp)から答えを取得する
コーディングテストで、「場合の数」、「最小/最大」、「可能なかどうか」を問う問題の多くはDPです。入力サイズが数百〜数千の場合、O(n²)のDPを疑ってみてください。
DPではない問題と区別する
| 信号 | DPの可能性 |
|---|---|
| 「最小/最大のコストで〜を行う」 | 高い |
| 「〜する方法の数を求める」 | 高い |
| 「〜が可能かどうかを判断する」 | 高い |
| 「ソートして選択すれば良い問題」 | 貪欲法を優先 |
| 「すべての経路を探索する必要がある問題」 | DFS/BFSを優先 |
DPと貪欲法はどちらも「最適部分構造」を活用しますが、貪欲法は後戻りせずに一方方向に進み、DPはすべての選択肢の結果をテーブルに記録します。
重要なポイント: 動的計画法は、「同じ計算を繰り返さない」という戦略です。メモ化（上から下、再帰+キャッシュ）とタブラ化（下から上、繰り返し+テーブル）の2つの方法で実装し、O(2^n)をO(n)またはO(n²)に改善します。