動的計画法（dynamic programming）
小さい問題の答えを表に残し、大きい問題はその表を見て組み立てる解き方。同じ計算を繰り返さずに済む。
もう少し詳しい説明
動的計画法は、小さい問題の答えを表に残して使い回す解き方です。
なぜ必要なのか
フィボナッチ数を例にします。「前の2つを足す」という決まりで並ぶ数です。
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)これを再帰でそのまま書くと、F(5) を求めるのに次の呼び出しが起きます。
| 求めるもの | 何回呼ばれるか |
|---|---|
| F(5) | 1回 |
| F(4) | 1回 |
| F(3) | 2回 |
| F(2) | 3回 |
| F(1) | 2回 |
同じ F(3) を2回計算しています。 nが大きくなると、この重複が一気に増えます。
一度求めた答えを表に書いておけば、2回目は読むだけで済みます。 これが動的計画法です。
2つの書き方
| 書き方 | 進む向き | 中身 |
|---|---|---|
| 下から上へ（表を順に埋める） | 小さいほうから | ループで表の先頭から埋めていく |
| 上から下へ（記録しながら再帰） | 大きいほうから | 再帰で呼び、求めた値を表に書き残す |
後者は、覚えておくという意味でメモ化と呼ばれます。どちらも「同じ計算を2回しない」という点は同じです。
使える条件
動的計画法が使えるのは、次の2つが成り立つときです。
| 条件 | 中身 |
|---|---|
| 小さい問題の答えで大きい問題が作れる | 全体の最適な答えが、部分の最適な答えから組み立てられる |
| 同じ小さい問題が何度も出てくる | 重複があるからこそ、記録が効く |
重複が無い問題では、記録しても速くなりません。 表を作る手間だけが増えます。
最長共通部分列での表
最長共通部分列の長さは、縦横に2つの列を並べた表で求めます。
表の各ますには、「縦の列の先頭からi文字」と「横の列の先頭からj文字」の最長共通部分列の長さを入れます。
| 2つの文字を比べた結果 | そのますに入れる値 |
|---|---|
| 同じ文字 | 左上のますの値 ＋ 1 |
| 違う文字 | 左のますと上のますのうち、大きいほう |
左上から順に埋めていくと、右下のますに全体の答えが出ます。
一度埋めたますは二度と計算しません。 ここが動的計画法の効き目です。
全部試す方法との差
| 方法 | 処理の回数の伸び方 |
|---|---|
| 部分列を全部作って比べる | 2のn乗（nは列の長さ） |
| 表を埋める | m × n（mとnは2つの列の長さ） |
n = 40 のとき、前者は約1兆、後者は1,600です。伸び方そのものが変わります。
他の題材
- ナップサック問題（重さの上限内で価値を最大にする選び方）
- 最短経路（分かれ道のある経路の中で最も短いもの）
- 編集距離（文字列を別の文字列に直すのに必要な手数）
どれも「小さい答えから組み立てる」形に書き直せる問題です。
試験ではこう出る
科目A（旧・午前）では、解き方の名前と中身の対応が問われます。全探索、貪欲法、分割統治法と並べて出ます。
| 解き方 | 特徴 |
|---|---|
| 動的計画法 | 小さい答えを記録して使い回す |
| 貪欲法 | その場で良く見えるほうを選び、見直さない |
| 分割統治法 | 半分に分けて解き、合わせる。重複は前提にしない |
| 全探索 | 候補をすべて試す |
応用情報の午後（プログラミング）では、表を埋める処理を擬似言語で読む形で出ます。設問は、表のあるますの値や、ループの中の式を問います。表の意味を1行で言えるようにしておくと、式が追えます。
関連する用語
- 部分列と最長共通部分列
- 動的計画法の代表的な題材。表を埋めて長さを求める
- 再帰
- 同じ分け方を再帰で書くと、同じ計算を何度も繰り返す
- 計算量
- 全部試す方法と表を使う方法で、伸び方が変わる
- 配列と二次元配列
- 表そのものの入れ物
ミニクイズ
動的計画法の特徴として、最も適切なものはどれか。
正解は 3番：小さい問題の答えを記録しておき、大きい問題を解くときにそれを読み出して使う
動的計画法は、問題を小さい問題に分け、その答えを表などに記録しておく解き方です。同じ小さい問題が何度も出てきても、記録を読み出すだけで済みます。すべての候補を順に試すのは全探索です。その時点で最も良く見える選択を続けるのは貪欲法で、あとで見直さない点が違います。半分に分けて絞るのは二分探索の考え方です。
この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）
最終更新：2026-11-09