動的計画法（DP）とは（全体像）
動的計画法は、「大きな問題を小さな問題に分け、小さな問題の答えをメモして使い回す」ことで、むだな計算を消す手法。アルゴリズムの強力な道具の1つだ。
たとえばフィボナッチ数列を素朴に再帰で計算すると、同じ計算を何度も繰り返して爆発的に遅くなる（O(2^n)）。一度計算した答えをメモしておけば、繰り返しが消えてO(n)まで速くなる——これがDPの効果だ。
ただし、どんな問題でも使えるわけではなく、2つの条件がそろう必要がある。
- 最適部分構造 … 全体の最適解が、部分の最適解の組み合わせで作れる。
- 部分問題の重複 … 同じ小さな問題が、何度も出てくる。
詳しく：2要件と2方式だけ覚えれば戦える
ここが記事の心臓部。まずはDPが使える2つの条件。
DPが使える2要件
| 要件 | 内容 |
|---|---|
| 最適部分構造 | 全体の最適解＝部分の最適解の組み合わせ |
| 部分問題の重複 | 同じ小さな問題が何度も出てくる |
この2つがそろって初めてDPが効く。「どんな問題でもDPで解ける」わけではない、というのが大事な注意点だ。
次に、実装の2方式。
DPの実装2方式
| 方式 | やり方 |
|---|---|
| トップダウン（メモ化再帰） | 再帰で解きつつ、計算した答えをメモして使い回す |
| ボトムアップ（表埋め） | 小さい問題から順に表を埋めていく（繰り返し） |
トップダウンは、再帰で大きい問題から下りつつ、途中の答えをメモする（直感的）。ボトムアップは、いちばん小さい問題から表を順に埋めていく（メモリ効率がよい）。どちらも「答えを使い回す」点は同じだ。つまり、上から下りるか下から積むかの違いで、メモして使い回す核心は変わらない、というわけだね。
なお、「DP＝メモ化」ではない。メモ化はDPの実装方式（トップダウン）の1つで、DPはもっと広い考え方だ。代表的なDPの問題には、フィボナッチ、ナップサック問題（限られた容量で価値を最大に）、最長共通部分列（2つの文字列の共通部分）などがある。
わかりやすく言い換えると
要するに、DPは「一度解いた小問題の答えをメモ帳に書いて使い回す」ことだ。
①メモなし … フィボナッチを素朴に計算すると、同じ小問題を何度も解き直して大渋滞（O(2^n)）
②メモあり（DP） … 一度解いた答えをメモに書き、次からはメモを見るだけ。むだな解き直しが消える（O(n)）
実装は、上から下りてメモする「トップダウン」と、下から表を埋める「ボトムアップ」の2通り。どちらも「同じ計算を二度しない」のが核心、というわけだね。
試験のツボ
🔴 一番出る：DPが使える2要件
①最適部分構造（全体最適＝部分最適の組み合わせ）
②部分問題の重複（同じ計算が何度も出てくる）
🔴 次に出る：実装2方式
①トップダウン＝メモ化再帰（再帰しつつメモ）
②ボトムアップ＝表埋め（小さい問題から順に）
🟡 押さえると安定：効果と代表例
①フィボナッチがO(2^n)からO(n)に速くなる
②ナップサック問題・最長共通部分列などが代表
よくある間違い
①「動的計画法はメモ化とまったく同じものである」→ ✗ メモ化はDPの実装方式（トップダウン）の1つ。DPはもっと広い考え方。
②「どんな問題でも動的計画法で解ける」→ ✗ 最適部分構造と部分問題の重複の2要件がそろう必要がある。
③「動的計画法はむだな計算を増やして遅くする手法である」→ ✗ むだな計算を使い回して減らし、速くする手法（フィボナッチはO(2^n)→O(n)）。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（DPの効果）
動的計画法（DP）の効果に関する次の記述のうち、正しいものはどれか。
- 小問題の答えを使い回し、フィボナッチをO(2^n)からO(n)に速くする
- 小問題の答えを毎回捨てるため、計算量はかえってO(2^n)に増えてしまう
- 動的計画法はデータを並べ替えるだけの手法で、計算の高速化とは無関係だ
- 動的計画法はメモを一切使わず、同じ計算を何度も繰り返す手法のことである
解答は 1 だよ。
DPは小問題の答えをメモして使い回すことで、むだな計算を消すんだ。素朴な再帰だとO(2^n)で爆発するフィボナッチが、DPでO(n)まで速くなるよ。
選択肢2は「毎回捨てる・増える」が誤り。選択肢3は「並べ替えるだけ」が誤り。選択肢4は「メモを使わず繰り返す」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | メモして使い回しO(2^n)→O(n) |
| 2 | ✗ | 捨てずに使い回す |
| 3 | ✗ | 計算の高速化に関わる |
| 4 | ✗ | メモして繰り返しを消す |
オリジナル問題2（2方式）
動的計画法の実装方式に関する次の記述のうち、正しいものはどれか。
- 実装はトップダウンの1方式だけで、表を埋めるやり方は存在しないものである
- 実装はボトムアップの1方式だけで、再帰を使うやり方は存在しないものだ
- トップダウン（メモ化再帰）とボトムアップ（表埋め）という2方式がある
- 実装方式はDPごとにランダムで、決まったやり方はないものとされている
解答は 3 だよ。
DPの実装にはトップダウン（メモ化再帰）とボトムアップ（表埋め）の2方式があるんだ。上から下りてメモするか、下から表を埋めるかの違いだね。
選択肢1・2は「1方式だけ」が誤り。選択肢4は「ランダム」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | ボトムアップもある |
| 2 | ✗ | トップダウンもある |
| 3 | ✓ | トップダウンとボトムアップの2方式 |
| 4 | ✗ | 決まった2方式がある |
オリジナル問題3（適用条件）
動的計画法が使える条件に関する次の記述のうち、正しいものはどれか。
- どんな問題でも動的計画法で必ず解ける、万能の手法であるとされている
- 最適部分構造と部分問題の重複の2つがそろうと、動的計画法がよく効く
- 部分問題がいっさい重複しない問題ほど、動的計画法の効果が大きくなる
- 動的計画法はメモ化と同じもので、適用できる条件はとくにないものである
解答は 2 だよ。
DPは最適部分構造（全体最適＝部分最適の組み合わせ）と部分問題の重複（同じ計算が何度も）の2つがそろうと効くんだ。どんな問題でも使えるわけではないよ。
選択肢1は「どんな問題でも・万能」が誤り。選択肢3は「重複しないほど効果大」が逆。選択肢4は「メモ化と同じ・条件なし」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 2要件が必要で万能ではない |
| 2 | ✓ | 最適部分構造＋部分問題の重複 |
| 3 | ✗ | 重複があるほど効く |
| 4 | ✗ | 2要件という条件がある |
まとめ
押さえどころ
- 🔴 DPの効果 ＝ 小問題の答えをメモして使い回し、むだな計算を消す（フィボナッチO(2^n)→O(n)）。
- 🔴 2方式 ＝ トップダウン（メモ化再帰）とボトムアップ（表埋め）。
- 🟡 適用条件 ＝ 最適部分構造と部分問題の重複の2要件がそろうと効く（DP＝メモ化ではない）。
次に学ぶ
- 再帰（末尾再帰・メモ化） ── DPのトップダウン実装で使う「メモ化」の基礎。再帰とDPのつながりが見える。
- 擬似言語の再帰 ── DPの土台になる再帰のトレース。科目Bでの読み解き方が深まる。
執筆: SikakuQuest編集部