動的計画法とは（全体像）
動的計画法（DP）とは、大きな問題を、小さな「部分問題」に分けて解き、その結果を覚えておくことで、効率的に答えを出す設計技法のことだ。
カギになるのが、メモ化。一度計算した答えを、メモ帳に書いておくイメージだ。同じ計算がまた必要になったら、計算し直さずに、メモを見るだけですむ。だから、ムダな計算が減って、速くなる。
ここで一番のポイント。動的計画法は、「部分問題への分割」と「メモ化」の2つで成り立つ。たとえば、同じ計算を何度もくり返してしまう処理を、メモ化することで、とても遅い（指数時間）状態から、現実的な速さ（多項式時間）へ改善できることがある。
詳しく：2つの要素と、向き不向き
ここが心臓部。ポイントを表で押さえよう。
動的計画法のポイント
| 項目 | やさしい意味 |
|---|---|
| 部分問題への分割 | 大きな問題を、小さな問題に分ける |
| メモ化 | 一度計算した結果を覚えておく |
| 効果 | 同じ計算をくり返さず、速くなる |
| 向き | 部分問題に分けられる問題に向く |
動的計画法の効果は、同じ計算をくり返さないことにある。一度出した答えを覚えておくので、ムダがなくなる。
ただし、注意点もある。どんな問題でも、動的計画法で速くできるわけではない。「小さな部分問題に分けられて、その結果を組み合わせれば答えが出る」という構造が必要だ。「動的計画法は、どんな問題にも使える」と思い込むと誤りになる。なお、動的計画法イコール再帰、ではない。再帰は実現の一手段で、本質は「部分問題＋メモ化」だ。
わかりやすく言い換えると
身近なたとえで整理しよう。
動的計画法は、「一度計算した答えをメモ帳に書いておき、また必要になったら、計算せずメモを見る」イメージ。同じ計算を、二度しないですむ。
「部分問題に分ける」というのは、大きな問題を、小さな問題のかたまりに分けること。要するに、小分けにして、結果を組み合わせる。
「向き不向きがある」というのは、部分問題に分けられる問題に向くこと。つまり、どんな問題にも万能で使える、というわけではない。
試験のツボ
🔴 一番出る：動的計画法の正体
①部分問題に分けて、結果をメモ化して、効率的に解く技法
②2要素は「部分問題への分割」＋「メモ化」
🔴 次に出る：メモ化の効果
①一度計算した結果を覚えておき、同じ計算をくり返さない
②ムダな計算が減って、速くなる（指数時間→多項式時間など）
🟡 押さえると安定：向き不向き
①部分問題に分けられる問題に向く
②どんな問題にも万能で使えるわけではない
よくある間違い
①「動的計画法は、どんな問題でも速くできる万能の方法だ」→ ✗ 部分問題に分けられる構造が必要。万能ではない。
②「動的計画法イコール再帰のことだ」→ ✗ 再帰は一手段。本質は「部分問題への分割」＋「メモ化」。
③「動的計画法は、同じ計算を何度もくり返す方法だ」→ ✗ 逆で、メモ化して同じ計算をくり返さないことで、速くする方法。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（動的計画法の正体）
動的計画法（DP）に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
- 部分問題に分け、結果をメモ化して、効率的に解く設計技法である
解答は 4 だぱん。
動的計画法は、部分問題に分け、結果をメモ化して、効率的に解く設計技法なんだぱん。一度計算した答えをメモするイメージだぱん。
選択肢1は給与計算、選択肢2は請求書の事務、選択肢3は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✗ | 請求書の事務の話 |
| 3 | ✗ | 広告活動ではない |
| 4 | ✓ | 部分問題＋メモ化で効率化で正しい |
オリジナル問題2（メモ化の効果）
動的計画法のメモ化の効果に関する次の記述のうち、最も適切なものはどれか。
- 社員の給与を計算するときだけ、効果が出るとされているものである
- 取引先への請求書の枚数しだいで、効果が決まるとされているものだ
- 同じ計算をくり返さずにすむので、ムダな計算が減って速くなるのだ
- 同じ計算を何度もくり返すので、かえって遅くなるとされているのだ
解答は 3 だぱん。
メモ化の効果は、同じ計算をくり返さずにすむので、ムダが減って速くなることなんだぱん。一度出した答えを覚えておくからだぱん。
選択肢1の給与、選択肢2の請求書、選択肢4の「遅くなる」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のときだけではない |
| 2 | ✗ | 請求書の枚数で決まるのではない |
| 3 | ✓ | 同じ計算をくり返さず速くなるで正しい |
| 4 | ✗ | くり返さないので速くなる |
オリジナル問題3（向き不向き）
動的計画法が向く問題に関する次の記述のうち、最も適切なものはどれか。
- 部分問題に分けられる問題に向く（どんな問題にも万能ではない）
- 社員の給与を計算する問題だけに向くものだとされているものだ
- 取引先へ請求書を郵送する問題だけに向くとされているものである
- どんな問題でも、必ず速くできる万能の方法だとされているものだ
解答は 1 だぱん。
動的計画法は、部分問題に分けられる問題に向く（どんな問題にも万能ではない）んだぱん。分けて組み合わせられる構造がいるんだぱん。
選択肢2の給与、選択肢3の請求書、選択肢4の「万能」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 部分問題に分けられる問題に向くで正しい |
| 2 | ✗ | 給与計算の問題だけではない |
| 3 | ✗ | 請求書の問題だけではない |
| 4 | ✗ | 万能ではない |
まとめ
押さえどころ
- 🔴 動的計画法（DP） ＝ 部分問題に分け、結果をメモ化して、効率的に解く設計技法。
- 🔴 メモ化の効果 ＝ 同じ計算をくり返さないので、ムダが減って速くなる（指数時間→多項式時間など）。
- 🟡 向き不向き ＝ 部分問題に分けられる問題に向く。どんな問題にも万能ではない。
次に学ぶ
- 再帰 ── 自分自身を呼び出す手法。動的計画法は、再帰にメモ化を組み合わせることもある。
- 計算量（ビッグオー記法） ── アルゴリズムの速さの目安。動的計画法は、計算量を大きく減らせることがある。
執筆: SikakuQuest編集部