動的計画法とは？
動的計画法（Dynamic Programming、DP）は、大きな問題を小さな部分問題に分けて解き、同じ部分問題を繰り返し計算せずに保存して再利用するアルゴリズム設計技法です。
「一度計算したものは二度と計算しない」——このシンプルなアイデアだけで、時間計算量を劇的に削減できます。
フィボナッチ数列：DPを理解する最良の例題
フィボナッチ数列は前の2つの数を足して次の数を作る数列です。
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
方法1：単純再帰 — O(2^n)
F(n)を求めるためにF(n-1)とF(n-2)をそれぞれ再帰呼出しすると、同じ値を何十回も重複計算します。
F(5)を求めるだけでF(3)が2回、F(2)が3回呼ばれます。nが大きくなると呼出回数が指数関数的に増加し、O(2^n)になります。
これがまさにDPが解決する問題です。
方法2：メモ化（Top-Down） — O(n)
一度計算した結果を配列やハッシュマップに保存し、同じ入力が来たら保存した値を返します。
核心アイデア：
- •F(n)を初めて計算したらmemo[n]に結果を保存
- •次にF(n)が必要になったらmemo[n]をそのまま返却
- •再帰構造は維持しつつ、重複計算を除去
各F(i)をちょうど1回だけ計算するためO(n)になります。
方法3：タビュレーション（Bottom-Up） — O(n)
小さな問題から順番に解いていく方式です。再帰の代わりにループを使用します。
核心アイデア：
- •dp[0] = 0, dp[1] = 1から開始
- •dp[2] = dp[0] + dp[1], dp[3] = dp[1] + dp[2], ...
- •ループでdp[n]まで順番に埋める
メモ化と時間計算量は同じですが、再帰呼出しのオーバーヘッドがなく、スタックオーバーフローの心配もありません。
3つの方法の比較
| 方法 | 時間計算量 | 空間計算量 | 特徴 |
|---|---|---|---|
| 単純再帰 | O(2^n) | O(n) スタック | 重複計算が深刻 |
| メモ化 | O(n) | O(n) | Top-Down、直感的 |
| タビュレーション | O(n) | O(n) → O(1)最適化可能 | Bottom-Up、安定的 |
DPを適用できる条件
1. 最適部分構造（Optimal Substructure）
大きな問題の最適解が小さな問題の最適解から構成できること。
2. 重複する部分問題（Overlapping Subproblems）
同じ部分問題が複数回繰り返されること。重複がなければ分割統治法で十分です。
フィボナッチの後のDP問題
フィボナッチを理解したら、次の問題に挑戦してみましょう。
コイン交換 — 与えられたコインで特定金額を作る最小コイン数
0/1ナップサック問題 — 重量制限内で価値を最大化する物の組み合わせ
LCS — 2つの文字列の最長共通部分列
AlgoNoteで直接確認しましょう
再帰呼出しがどのように重複するか、メモ化がどのように重複を除去するか、AlgoNoteでフィボナッチの再帰ツリーを視覚的に確認できます。DPの核心を目で理解してください。