【Common Lisp】
動的計画法（DP）の基本の考え方
（再帰で考え、表を順番に埋める）

by
  • DP（Dynamic Programming：動的計画法）は、再帰で解いた問題が計算時間がかかるときに使える解き方のアプローチです。
  • DPは、問題を捉える枠組みで、クイックソートや二分探索のような「決まった手順」ではありません。
  • ポイントは、配列を使って重複する部分問題を一度だけ解き、その結果を保存して再利用することです。
  • Common Lispでは、再帰で問題の構造を確認してから、make-arrayとloopで表を下から埋める形に移すと、変換の意味が見えやすくなります。

関連記事

1. 「DPで解く」とは？

競技プログラミングの解説を読んでいると、「DPで解く」という言葉を見かけます。

「DPで解く」とは何か BIT・クイックソート 決まった手順 使えばO(log n) 具体的なデータ構造 ・アルゴリズム ≠ DP（動的計画法） 問題を捉える「枠組み」 部分問題を保存して再利用する方針 ① 分割 大→小 ② 保存 結果を記録 ③ 再利用 指数→O(n) ベルマンが1950年代に定式化した多段階意思決定の最適化原理

てっきり「二分探索で解く」や「BITで解く」などのように、特定のアルゴリズムやデータ構造だと思っていたのですが、なんとなく腑に落ちません。

たとえば、フィボナッチ数列を「DPで解く」とは、こういうコードです。

(defun fib-dp (n)
  (let ((dp (make-array (1+ n) :initial-element 0)))
    (setf (aref dp 1) 1)
    (loop for i from 2 to n do
      (setf (aref dp i) (+ (aref dp (1- i)) (aref dp (- i 2)))))
    (aref dp n)))Code language: Lisp (lisp)

素直な解き方が宣言的（declarative）なのに対して、だいぶ処理が細かく明示されていて「命令的（imperative）」です。

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))Code language: Lisp (lisp)

つまり、途中の計算結果を make-arrayとloopを使って配列を埋める、ということで効率的になっています。
しかし、再帰呼び出しが深くならないようにループを使って、計算結果をキャッシュで保存して繰り返しを避ける、ということと「動的計画」という言葉がつながりません。

この解き方が「DP」と呼べるのは、問題が持つある種の構造に着目し「部分問題の答えを保存して再利用する」という方針を取り、その構造を利用しているからです。

1.1. DPは単一のアルゴリズムではない

たとえば、BIT（Binary Indexed Tree）は具体的なデータ構造で、「これを使えば区間和の更新と参照がO(log n)でできる」と決まっています1。
あるいは、クイックソートが「この手順を踏めば整列できる」という手続きです。

しかし、DPは層が違います。
「重複する部分問題を保存して再利用する」という設計の方針であり、「この見方で問題を整理すると、無駄な再計算を省ける」という考え方です。
その実装にBITを使うこともあります。

1.2. DPは意思決定理論

「動的計画法（DP：Dynamic Programming）」は、リチャード・ベルマンが1952年頃に提唱した、「複雑な意思決定で効率的に最適解を求めるための数学的な解法」です2。

ベルマンの念頭にあったのは特定のアルゴリズムではなく、ロケットの軌道制御や資源配分のような多段階意思決定問題を数学的に扱うことでした。
彼は、「各ステップの最適な決定が、次の状態を決める」という構造を「最適性の原理（Principle of Optimality）」として定式化して、部分最適化問題の解き方として広く影響を与えます3。

ただ、軍の研究予算を確保するためには、数学的な理論研究は不利だった、という実務的な理由もあり、「Dynamic Programming（動的な計画立案法）」という名前が選ばれました4。
1950年代当時は、「programming」の意味はまだコードを書くことではなく、スケジューリングや計画立案を指す言葉で5、兵站や軍事行動の最適化に役立てることが伝わります。

つまり、「動的計画」という言葉そのものは、数学や計算機科学の用語として生まれたわけではなく、「部分状態を少しずつ変えながら、先の選択を決めていく戦略」ぐらいの意味合いでとらえるとよいです。

2. DPが使える問題構造の条件

DP（動的計画法）で大事なのは、その考え方です。

  • 「大きな問題を、小さな部分問題に分ける」
  • 「同じ部分問題を何度も解かないように、答えを保存する」
  • 「保存した答えを使って、次の答えを作る」

という手法を定式化したものです。

今となっては「普通の解き方」にも見えますが、この定式化が重要なのは問題の構造に着目したことです。
DPが適用できる条件は二つあります。

  • 部分問題が重複すること、
  • 部分問題の最適解から全体の最適解を組み立てられること

どちらかが欠けると、DPを適用しても意味がありません。

2.1. 動的計画法と分割統治法や貪欲法の違い

DPは、「問題を解くアプローチ」の一つです。

問題を解くアプローチにはいくつもあります。

たとえば、DPに似た考え方に分割統治法（Divide and Conquer）があります。
しかし、こちらは部分問題が重複しない問題に適用され、具体的なアルゴリズムとしてマージソートなどがあります。

あるいは、貪欲法（greedy algorithm）はその場の最善手を選び続ける手法です。
これは、DPのように全パターンを記憶して比較するわけではありません。

3. 三つのアプローチを比べる

コインの両替問題で、三つのアプローチによるCommon Lispでの実装を見ていきます。

額面が1円、5円、10円のコインが無制限にあるとき、41円を作るのに必要な最小枚数を求めてください。

3.1. 総当たり法

もっともシンプルな考え方は、「総当たり法（brute-force search）」です。
素直に再帰を解くと、すべての組み合わせを試すことになります。

(defun coins-brute (amount coins)
  (if (= amount 0)
      0
      (loop for c in coins
            when (<= c amount)
            minimize (1+ (coins-brute (- amount c) coins)))))Code language: Lisp (lisp)

正しい答えが出ますが、同じamountを何度も計算しています。
coins-brute 41を計算する途中では、coins-brute 36が複数回呼ばれ、さらにその中で同じ値が繰り返し計算されます。
計算量は指数的に増えます。

3.2. 貪欲法

貪欲法は、その時点で使える最大の額面から選び続けます。

(defun coins-greedy (amount coins)
  (let ((sorted (sort (copy-list coins) #'>))
        (count 0))
    (dolist (c sorted count)
      (multiple-value-bind (q r) (floor amount c)
        (incf count q)
        (setf amount r)))))Code language: Lisp (lisp)

41円なら10円×4枚、1円×1枚で5枚という計算になり速いです。

ただし、今回はたまたまうまくいっていますが、額面によっては最適解を求められません。
たとえば、額面が1円、3円、4円のときに6円を作ると、貪欲法は4円+1円+1円の3枚を選びますが、最適解は3円+3円の2枚です6。

3.3. 動的計画法（DP）

DPは、0円から41円まで「この金額を作る最小枚数」を順番に求めて、表に埋めていきます。

(defun coins-dp (amount coins)
  (let ((dp (make-array (1+ amount) :initial-element most-positive-fixnum)))
    (setf (aref dp 0) 0)
    (loop for a from 1 to amount do
      (loop for c in coins
            when (<= c a)
            do (setf (aref dp a)
                     (min (aref dp a)
                          (1+ (aref dp (- a c)))))))
    (aref dp amount)))Code language: Lisp (lisp)

総当たり法と違うのは、表に埋めていくという考え方です。
そのため、記録表となる配列を dp という名前で確保することが多いです。

今回は、dp[a]は「金額aを作る最小枚数」を記録し、dp[0] = 0を出発点にdp[1]から順に埋めていきます。
dp[41]を求めるときにはdp[40]、dp[36]、dp[31]がすでに計算済みなので、そこから1枚足すだけです。

これにより、計算量はO(amount × コインの種類数)になります。

三つを並べると、こういう関係になります。

3つのアプローチ比較：コイン両替41円 アプローチ 計算量 最適解 特徴 総当たり brute-force 指数時間 △（時間） 同じ部分問題を 何度も計算 貪欲法 greedy O(n log n) △（局所的） 局所最善を選択 全体最適を保証せず 動的計画法 DP O(n × 種類数) ◎ 部分問題を一度だけ 解いて保存・再利用 DPは「正しさ」と「速さ」を両立する — 最適部分構造があるから成り立つ
アプローチ計算量最適解特徴
総当たり指数時間保証する同じ部分問題を何度も解く
貪欲法O(n log n)保証しない局所的な最善手を選ぶ
DPO(amount × coins)保証する部分問題を一度だけ解いて保存する

DPは総当たりの「正しさ」と、貪欲法に近い「速さ」を両立するための手法です。
これは、このコインの両替問題が最適部分構造を持っているから成り立ちます。

この問題の最適部分構造は、たとえば、最後に5円玉を足して41円にするなら、その前の36円も最小枚数で作れている必要がある、ということです。
36円の部分に無駄があれば、41円全体も最小にはならないからです。

4. 動的計画法の深堀り

フィボナッチ数列もDPによって効率化できる問題です。

定義は、そのまま再帰になりますが、呼び出し回数が指数的に増える構造になっています。

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))Code language: Lisp (lisp)

fib(5)を解くにはfib(4)とfib(3)が必要で、fib(4)を解くにはfib(3)とfib(2)が必要、という依存関係をそのままコードにしているので、実行すると、fib(3)は2回、fib(2)は3回呼ばれます。
nが大きくなると呼び出し回数は指数的に増え、fib(40)あたりですでに体感できるほど遅くなります7。

4.1. トップダウンDPとメモ化

依存関係があるのに、複数呼び出しがあるなら、一度計算した結果を保存して使い回すのが有効です。

これが「メモ化（memoization）」です。
ちなみに、「memorization（暗記）」の誤植ではないです8。

(defun fib-memo (n)
  (let ((memo (make-array (1+ n) :initial-element nil)))
    (labels ((fib (i)
               (cond ((= i 0) 0)
                     ((= i 1) 1)
                     ((aref memo i))
                     (t (setf (aref memo i)
                              (+ (fib (- i 1)) (fib (- i 2))))))))
      (fib n))))Code language: Lisp (lisp)

memo[i]に値が入っていれば即座に返し、なければ計算して保存します。
再帰の構造はそのままですが、fib(3)が計算されるのは最初の1回だけになります。
計算量は O(n)になります。

これは、「トップダウンDP」と呼ばれます。
大きな問題から必要な部分問題へ降りながら、結果を保存していく形です9。

4.2. 表を下から埋める（ボトムアップDP）

メモ化再帰をさらに整理すると、再帰を使わずに小さい方から順に配列を埋める形にすることができます。

これは「ボトムアップDP」と呼ばれます。

(defun fib-dp (n)
  (let ((dp (make-array (1+ n) :initial-element 0)))
    (setf (aref dp 1) 1)
    (loop for i from 2 to n do
      (setf (aref dp i) (+ (aref dp (1- i)) (aref dp (- i 2)))))
    (aref dp n)))Code language: Lisp (lisp)

「fib(i)の答え」は、dp[i]に記録し、dp[0] = 0、dp[1] = 1を出発点に、dp[2]から順に埋めます。
ボトムアップDPのメリットは、計算順序を明示的に制御できること。
dp[i]を計算するときにはdp[i-1]とdp[i-2]がかならず埋まっているので、再帰もメモの参照も不要です。

n が大きくクエリが1回だけなら、メモリを節約することもできます。
フィボナッチなら直前の2つだけ持てばよいので、配列を変数2つに落とせます。

(defun fib-dp-compact (n)
  (if (< n 2)
      n
      (loop for i from 2 to n
            with a = 0 and b = 1
            do (psetf a b b (+ a b))
            finally (return b))))Code language: Lisp (lisp)

4.3. DPを読むための3点（状態、遷移、初期値）

DPのコードを読むとき、状態、遷移、初期値の三つを探すと構造が見えます。

DP実装の2方向とコードの読み方 トップダウンDP fib(5) 計算 fib(4) 計算 fib(3) 再利用 必要な部分問題だけ解く ボトムアップDP dp[0] 0 1 1 2 3 5 順に埋める 全セルを下から積み上げる DPコードを読む3点 状態 dp[i]の意味 遷移 前からの式 初期値 出発点 再帰で構造を確認 → メモ化 → ループで表を埋める、という流れで理解が深まる
  • 状態はdp[i]が何を表すかです。
    フィボナッチなら「i番目の値」、コインなら「金額iを作る最小枚数」です。
    状態の定義が曖昧なままだと、遷移式が書けません。
  • 遷移はdp[i]を前の値からどう作るかです。
    フィボナッチならdp[i] = dp[i-1] + dp[i-2]、コインならdp[i] = min(dp[i-c] + 1)で、この式が問題の構造を直接表しています。
  • 初期値は計算の出発点です。
    フィボナッチならdp[0] = 0, dp[1] = 1、コインならdp[0] = 0です。
    初期値が間違っていると、正しい遷移式を書いても答えがずれます。

この三点が揃って、はじめてDPのコードは読めます。
DPを書くときは状態の定義から始めるのが確実です。

5. 再帰の何がDPに変わったか

三つのコードを並べると、対応関係が見えます。

再帰（総当たり）トップダウンDPボトムアップDP
同じ部分問題何度も計算する初回だけ計算して再利用一度だけ書き込んで参照
呼び出し順序必要な順に再帰必要な順に再帰ループで明示的に制御
計算量O(φ^n)O(n)O(n)
状態関数の引数 i関数の引数 i配列の添字 (aref dp i)
遷移再帰呼び出し再帰呼び出し＋保存setfでセルを更新
初期値ベースケース (cond ...)ベースケース (cond ...)(setf (aref dp 0) 0)

再帰は「この問題を解くには何が必要か」をトップダウンで自然に表現できます。
部分問題が重複せず再帰がそのまま効率的に動くなら、それは分割統治法のパターンです。

しかし、部分問題が重複するとき、再帰は簡潔だが非効率になります。
このような「再帰で見えた構造を効率よく実行する」ための漸進的なアプローチが動的計画法です。
まずは、メモ化（トップダウンDP）、そしてループによる表の埋め立て（ボトムアップDP）に切り替えていくことで、部分最適解を効率よく統合して回答を求めます。

(defun fib-dp (n)
  (let ((dp (make-array (1+ n) :initial-element 0)))
    (setf (aref dp 1) 1)
    (loop for i from 2 to n do
      (setf (aref dp i) (+ (aref dp (1- i)) (aref dp (- i 2)))))
    (aref dp n)))Code language: Lisp (lisp)

つまり、fib-dpは、loop for i, dp[i] = (...) という部分が、ボトムアップによる表の埋め立て、というわけです。

5.1. 再帰と問題解決のパターン

再帰で表現できる問題の解き方として、分割統治法や動的計画法（DP）のほかに、貪欲法、後退法（バックトラッキング）、分枝限定法（branch and bound：枝刈り）があります。

  • 貪欲法は、再帰で書けることも多いですが、その時点の最善手だけを選ぶことで再帰が浅く終わらせます（ただし、全体最適を取りこぼすことがあります）。
  • 後退法（バックトラッキング）は、再帰で全探索しながら、条件を満たさない枝を途中で打ち切る手法です。
  • 分枝限定法は、バックトラッキングより強く、現時点での最良解より悪くなると分かった枝を積極的に捨てます。
  1. BITはPeter Fenwickが1994年に発表したデータ構造で、累積和の更新と参照を両方O(log n)で行えます。競技プログラミングでは頻繁にDPと組み合わせて使われるため、同列に見えることが多いです。 – Peter M. Fenwick, “A New Data Structure for Cumulative Frequency Tables”, Software: Practice and Experience, 1994
  2. Wikipediaによると、ベルマンは1949年からRAND研究所に勤務し、DPを1950年代にかけて段階的に定式化しました。1952年に最初の論文、1957年に著書”Dynamic Programming”をプリンストン大学出版から刊行しています。 – Richard E. Bellman – Wikipedia
  3. ベルマン自身はこれを「最適性の原理（Principle of Optimality）」と呼んでいました。「最初の状態と最初の決定がどうであれ、残りの決定は最初の決定がもたらした状態に対して最適でなければならない」という定式化です。コンピュータサイエンスでは”optimal substructure”と呼ばれます。 – Bellman equation – Wikipedia
  4. ベルマンは1984年の自伝『Eye of the Hurricane』の中でこのエピソードを語っています。当時の国防長官ウィルソンが”research”や”mathematics”という言葉に強い拒否反応を示していたため、それらを含まない名前を意図的に選んだと述べています。ただしWikipediaによると、ベルマンが”dynamic programming”という語を最初に使った論文（1952年）はウィルソンが国防長官に就任する前（1953年）であり、エピソードの正確性には注釈がついています。 – Dynamic programming – Wikipedia
  5. “programming”は当時、線形計画法（linear programming）や数理計画法（mathematical programming）でも使われていた用語で、「最適な計画・スケジュールを立てること」を意味していました。この用法は現在も「mathematical programming」という言い方で残っています。 – Dynamic programming – Wikipedia
  6. 貪欲法がコイン問題で最適解を保証するのは、コインの額面が特定の条件を満たす場合に限ります。日本円（1円、5円、10円、50円、100円、500円）やUSドル（1セント、5セント、10セント、25セント）は貪欲法で最適解が出る設計になっていますが、任意の額面では成立しません。貪欲法が最適解を保証するかどうかを判定すること自体はO(n²)で可能ですが、一般的なコイン問題の最小枚数を求めることはNP困難です。 – Greedy algorithm – Wikipedia
  7. 素朴な再帰によるフィボナッチの計算量はO(2^n)と説明されることが多いですが、より正確にはO(φ^n)です。φは黄金比（約1.618）で、フィボナッチ数列がφの累乗に比例して増加することから導かれます。実用上はn=50を超えると現代のマシンでも秒単位の待ちが発生します。 – Time complexity of recursive Fibonacci program – GeeksforGeeks
  8. 「メモ化（memoization）」という用語は、英国の人工知能研究者ドナルド・ミッキーが1968年に発表した論文”Memo Functions and Machine Learning”（Nature誌）で作った言葉です。ラテン語のmemorandom（記憶されるべきもの）に由来し、”memorization（暗記）”とは別の語です。 – Memoization – Wikipedia
  9. 「トップダウン」と「ボトムアップ」という呼び方は、問題を分解する方向を指しています。トップダウンは大きな問題から必要な部分問題へ再帰的に降りる形、ボトムアップは最小の部分問題から順に積み上げる形です。どちらも同じ問題を解きますが、実装上の特性が異なります。トップダウンは必要な部分問題だけを解くのに対して、ボトムアップはすべてのセルを埋めます。 – Dynamic programming – Wikipedia