動的計画法とベルマンの原理

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：整数計画とは・LP緩和・代表的な組合せ問題　|　関連：最短経路問題（ダイクストラ・ベルマンフォード）

要点（BLUF）

動的計画法（DP）は、問題を 重なり合う部分問題に分け、小さい方から解いて表に貯めて再利用する。
成立条件は ベルマンの最適性原理：「全体の最適解は、部分問題でも最適である」。
分枝限定（分枝限定法）・切除平面（切除平面法）と並ぶ、離散・逐次最適化の 第3の柱。最短路（最短経路問題（ダイクストラ・ベルマンフォード））・多段階確率計画（確率計画法）の基盤。

概念 ── 部分問題を貯めて再利用する

多くの最適化は「逐次的な決定の積み重ね」として書ける（どの品目を入れるか、どの都市へ進むか、各期にいくら在庫するか）。素朴に全選択肢を試すと指数爆発（計算複雑性とNP困難の地図）。動的計画法は、同じ部分問題が何度も現れることを利用し、一度解いた部分問題の答えを表に記録（メモ化）して再利用する。

ベルマンの最適性原理

最適方策の部分方策もまた最適である。

つまり「始点から終点への最短経路の途中点を通る部分も、その途中点までの最短経路になっている」（最短経路問題（ダイクストラ・ベルマンフォード））。この性質があると、最適値を 部分問題の最適値の漸化式（ベルマン方程式） で書ける：

V(s) = \min_{a}\ \bigl\{\, c(s,a) + V(s') \,\bigr\}

$s$ が状態、 $a$ が 決定（行動）、 $s'$ が次状態、 $V$ が 価値関数（その状態からの最適値）。状態を小さい方から（または後ろ向きに）解けば、各状態を1回ずつ計算するだけで全体最適が得られる。

graph TD
  A["問題を状態と段階に分解"] --> B["最適性原理が成立するか"]
  B -->|"はい"| C["ベルマン方程式(漸化式)を立てる"]
  C --> D["小さい部分問題から表を埋める(メモ化)"]
  D --> E["最終状態の値が全体最適"]
  B -->|"いいえ"| F["DPは適用不可(別手法)"]

DP の3条件

最適部分構造：全体最適が部分問題の最適から構成できる（最適性原理）。
部分問題の重複：同じ部分問題が何度も現れる（だからメモ化が効く）。
状態の明確な定義：「何が決まれば残りが定まるか」を状態に取る。状態数 × 遷移数が計算量。

Pythonで0/1ナップサックを解く

状態を「最初の $i$ 品目・容量 $c$ 」とし、 $dp[i][c]=$ その範囲での最大価値。漸化式は「品目 $i$ を入れない vs 入れる」の最大（ベルマン方程式）。第3章のナップサック（代表的な組合せ問題）を DP で解く。

import numpy as np

values, weights, capacity = [60, 100, 120], [10, 20, 30], 50
n = len(values)
dp = np.zeros((n+1, capacity+1), dtype=int)   # dp[i][c]: i品目,容量cの最大価値

for i in range(1, n+1):
    for c in range(capacity+1):
        dp[i][c] = dp[i-1][c]                  # 品目iを入れない
        if weights[i-1] <= c:                  # 入れられるなら
            dp[i][c] = max(dp[i][c],
                           dp[i-1][c-weights[i-1]] + values[i-1])  # 入れる方と比較
print(f"最大価値 = {dp[n][capacity]}")

# どの品目を選んだか復元
c, chosen = capacity, []
for i in range(n, 0, -1):
    if dp[i][c] != dp[i-1][c]:                 # 値が変わった = 品目iを入れた
        chosen.append(i-1); c -= weights[i-1]
print(f"選んだ品目(0始まり) = {sorted(chosen)}")

実行結果：

最大価値 = 220
選んだ品目(0始まり) = [1, 2]

DP は最大価値 220（品目1と2）を返し、分枝限定や整数計画（代表的な組合せ問題）と一致。状態数は $n \times W = 3\times50$ だけで、 $2^n$ の全探索を避けた。これが 擬多項式時間（容量 $W$ に比例）で、ナップサックが「弱 NP 困難」と呼ばれる理由（計算複雑性とNP困難の地図）。

貪欲法との違い ── コイン両替

DP が貪欲法より強いことをコイン両替で見る。コイン $[1,5,12]$ で 15 円を最小枚数で作る。貪欲（大きい順）は $12+1+1+1=4$ 枚だが、DP は最適 $5+5+5=3$ 枚を見つける。

coins, amount = [1, 5, 12], 15
INF = 10**9
dp = [0] + [INF]*amount                # dp[a]: a円を作る最小枚数
for a in range(1, amount+1):
    for coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], dp[a-coin] + 1)   # ベルマン方程式
print(f"{amount}円の最小コイン枚数 = {dp[amount]}")

実行結果：

15円の最小コイン枚数 = 3

DP は 3 枚（ $5\times3$ ）。貪欲法は「その場で最大のコイン」を取って 4 枚になり 最適でない。DP は全部分問題を考慮するので、貪欲が見逃す組合せを捉える ── 最適性原理が成り立つ問題では、DP が厳密最適を保証する。

数式の直観的意味

DP の力は「指数的な探索を、状態空間上の 多項式的な表計算に畳む」こと。鍵は状態の取り方：状態とは「過去の決定のうち、未来の最適決定に影響する情報の要約」（十分統計量）。ナップサックなら「残り容量と残り品目」さえ分かれば、そこに至る経路の詳細は不要 ── だから経路ごとに分けず、状態ごとにまとめられる。ベルマン方程式 $V(s)=\min_a\{c(s,a)+V(s')\}$ は最適値の 不動点方程式で、最短路（最短経路問題（ダイクストラ・ベルマンフォード））のベルマンフォード法がこれを反復で解くのと同じ構造。DP は分枝限定（分枝限定法）が「上界で枝を刈る」のと違い、部分問題の 完全な最適値を貯めて再利用する ── 状態数が小さければ DP、状態爆発するなら分枝限定、という使い分けになる。多段階確率計画（確率計画法）や強化学習（価値反復）も、このベルマン方程式の拡張。

⚠️ よくある誤解・落とし穴

最適性原理が成り立たないと DP は使えない：部分最適が全体最適に繋がらない問題（一部の制約付き経路問題）では誤る。
状態の設計が命：状態に必要な情報を落とすと誤り、入れすぎると状態爆発。十分統計量を見抜く。
擬多項式は「多項式」ではない：ナップサック DP は容量 $W$ に比例。 $W$ が指数的に大きい（桁数で効く）と非実用的。
貪欲法は最適性原理＋マトロイド構造のときだけ最適。一般には DP（または厳密解法）が要る。