## 2. 準備：計算モデルと記号
計算量は単位費用 RAM モデル（
）で数えます。加減算・比較・配列の添字アクセスを 1 ステップとします。$O$ 記法については [計算量と O 記法](/computer-science/algorithms/complexity-and-big-o) を、配列が添字アクセスを $O(1)$ でできることについては [基本的なデータ構造](/computer-science/algorithms/data-structures)（
）を前提とします。有向非巡回グラフ（DAG）と位相ソートは [グラフアルゴリズム](/computer-science/algorithms/graph-algorithms)（DAG であることの特徴づけは
）の内容を使います。
記号を決めておきます。
- $[n] = \{1, 2, \ldots, n\}$ とし、$[0] = \emptyset$ とします。
- $\mathbb{Z}_{\ge 0}$ は非負整数全体、$\mathbb{Z}_{\ge 1}$ は正整数全体を表します。
- $\varphi = \dfrac{1 + \sqrt{5}}{2} = 1.6180\ldots$ を黄金比とします。$\varphi$ は $t^2 = t + 1$ の正の解なので、$\varphi^2 = \varphi + 1$ が成り立ちます。この関係だけを後で使います。
- 部分集合 $S \subseteq [n]$ と数列 $(a_i)$ に対し、$a(S) = \sum_{i \in S} a_i$ と略記します。$a(\emptyset) = 0$ です。
## 3. 動的計画法の枠組み
まず、動的計画法という手法を一般的な形で書き下します。個々の問題ごとに計算量を数え直さずに済むようにするためです。
有限集合 $S$ と、各 $s \in S$ に対して定まる値 $V(s)$ の組が次の 3 条件を満たすとき、これを**部分問題族**と呼ぶことにします。
1. 各 $s \in S$ に、$S$ の元からなる有限列 $D(s) = (s_1, \ldots, s_{k_s})$ が定まっている。これを $s$ の**依存先**と呼びます。
2. 各 $s \in S$ に関数 $g_s$ が定まっていて、$V(s) = g_s\bigl(V(s_1), \ldots, V(s_{k_s})\bigr)$ が成り立つ。
3. 有向グラフ $G = (S, E)$、$E = \bigl\{ (s', s) : s \in S,\ s' \in D(s) \bigr\}$ が閉路をもたない（DAG である）。
$k_s = 0$ である $s$、すなわち依存先をもたない部分問題を**基底**と呼びます。基底では $V(s) = g_s()$ は定数として直接与えられます。
条件 3 の辺は「依存される側 $\to$ 依存する側」の向きに引いてあります。ですから $G$ の位相順序に沿って計算すれば、必要な値は必ず先に手に入っています。この観察をそのまま定理にしたのが次です。
この定理の使い方は決まっています。**部分問題を何個作ったか（$N$）と、1 つの部分問題を解くのに何ステップかかるか（$c$）を数える。掛ければ計算量が出る。** 以降のフィボナッチ、ナップサック、編集距離の計算量は、すべてこの一言で片づきます。
### 3.1. トップダウンとボトムアップ
の証明では位相順序を先に求めましたが、実装では 2 つの流儀があります。
2 つの流儀を比べます。
| | メモ化再帰（トップダウン） | 表計算（ボトムアップ） |
|---|---|---|
| 計算順序 | 再帰が依存関係を自動的に辿る | 位相順を人が決めてループに書く |
| 実際に解く部分問題 | 必要なものだけ（
の $R$） | 表の全マス |
| 実装 | 素朴な再帰に表を足すだけ | ループの順序を設計する必要がある |
| 弱点 | 再帰の深さ制限、呼び出しのオーバーヘッド | 使わない部分問題も解いてしまう |
| 領域の削減 | しにくい | 「直前の行だけ持つ」等がやりやすい |
どちらも
と同じオーダーの計算量になります。以下では両方を使い分けます。
## 4. フィボナッチ数列：指数時間から線形時間へ
§1 で観察した重複を、まず定量化します。
$T(n)$ を、`fib_naive(n)` の実行中に起きる関数呼び出しの総数（最初の 1 回を含む）とする。$n \ge 0$ に対して
$$
T(n) = 2F_{n+1} - 1
$$
が成り立つ。さらに $n \ge 1$ に対して $2\varphi^{n-1} - 1 \le T(n) \le 2\varphi^{n} - 1$ であり、したがって $T(n) = \Theta(\varphi^n)$ である。
**等式。** $n$ に関する強い帰納法です。$n = 0$ のとき、`fib_naive(0)` は再帰せずに戻るので $T(0) = 1$。一方 $2F_1 - 1 = 2 \cdot 1 - 1 = 1$ で一致します。$n = 1$ のときも同様に $T(1) = 1$ で、$2F_2 - 1 = 2 \cdot 1 - 1 = 1$ です。$n \ge 2$ とし、$n$ 未満で成立を仮定します。`fib_naive(n)` は自分自身の 1 回に加えて `fib_naive(n-1)` と `fib_naive(n-2)` を呼ぶので
$$
T(n) = 1 + T(n-1) + T(n-2) = 1 + (2F_n - 1) + (2F_{n-1} - 1) = 2(F_n + F_{n-1}) - 1 = 2F_{n+1} - 1
$$
となります。最後の等号はフィボナッチ数の漸化式です。
**評価。** 補助的に、$m \ge 1$ に対して $\varphi^{m-2} \le F_m \le \varphi^{m-1}$ を示します。$m = 1$ では $\varphi^{-1} = 0.618\ldots \le 1 = F_1 \le \varphi^0 = 1$、$m = 2$ では $\varphi^0 = 1 \le 1 = F_2 \le \varphi^1$ で成立します。$m \ge 3$ とし、$m$ 未満で成立を仮定すると、§2 で確認した $\varphi^2 = \varphi + 1$ を使って
$$
F_m = F_{m-1} + F_{m-2} \ge \varphi^{m-3} + \varphi^{m-4} = \varphi^{m-4}(\varphi + 1) = \varphi^{m-4} \varphi^{2} = \varphi^{m-2},
$$
$$
F_m = F_{m-1} + F_{m-2} \le \varphi^{m-2} + \varphi^{m-3} = \varphi^{m-3}(\varphi + 1) = \varphi^{m-1}
$$
が得られます。この評価を $m = n+1$ に適用すれば $\varphi^{n-1} \le F_{n+1} \le \varphi^{n}$ であり、等式に代入して主張が出ます。$\varphi > 1$ なので $T(n)$ は指数的に増大します。
この式は具体的な数を入れると効きます。$T(50) = 2F_{51} - 1 = 40{,}730{,}022{,}147$、およそ $4.1 \times 10^{10}$ 回。1 秒間に $10^9$ 回の関数呼び出しをこなす計算機でも 40 秒です。$n = 100$ ではどうなるかは
で計算してもらいます。
### 4.1. 表を持てば線形になる
の言葉で書き直します。部分問題の添字集合は $S = \{0, 1, \ldots, n\}$、値は $V(k) = F_k$、依存先は $D(0) = D(1) = ()$（基底）、$k \ge 2$ では $D(k) = (k-1, k-2)$、遷移は $g_k(a, b) = a + b$ です。辺は $k$ の小さい方から大きい方へ向かうので閉路はなく、DAG の条件も満たされます。
上の部分問題族に
トップダウン（メモ化再帰）とボトムアップ（反復）の両方を書いておきます。
```python
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo: # すでに計算済みなら表を引くだけ
return memo[n]
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
def fib_table(n):
if n <= 1:
return n
a, b = 0, 1 # a = F(0), b = F(1)
for _ in range(2, n + 1):
a, b = b, a + b # (F(k-2), F(k-1)) -> (F(k-1), F(k))
return b
```
`fib_memo` は素朴な再帰に 3 行足しただけです。それでも
より、実際に本体が実行される部分問題は $R = \{0, 1, \ldots, n\}$ の $n+1$ 個だけになります。
$n = 10$ の表を実際に埋めます。左から順に $F_{k} = F_{k-1} + F_{k-2}$ を計算するだけです。
| $k$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $F_k$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
加算は 9 回、表のマスは 11 個です。一方、素朴な再帰の呼び出し回数は
## 5. 最適部分構造：使える条件と、壊れる例
フィボナッチ数は「値を計算する」問題でした。動的計画法が本領を発揮するのは最適化問題ですが、そこには追加の条件が要ります。
最適化問題の族 $\{P_s\}_{s \in S}$ があり、$P_s$ の最適値を $V(s)$ とします。各 $s \in S$ に対して依存先 $D(s) = (s_1, \ldots, s_k)$ と関数 $g_s$ が存在して
$$
V(s) = g_s\bigl(V(s_1), \ldots, V(s_k)\bigr)
$$
が成り立ち、かつ依存グラフが DAG になるとき、この問題族は**最適部分構造**をもつといいます。
言い換えると、$P_s$ の最適値が部分問題の**最適値だけ**から復元できる、ということです。ここが要点で、「部分問題の最適解を貼り合わせたものが実行可能解になる」ことと「実行可能解を分解すると部分問題の実行可能解になる」ことの両方が要ります。この確認に使う標準的な議論が**切り貼り論法**です。$P_s$ の最適解 $x$ を分解して得た部分解 $x_i$ が $P_{s_i}$ の最適解でないとすると、$x_i$ をより良い解に取り替えて（切って貼って）$x$ より良い $P_s$ の解が作れてしまい、$x$ の最適性に反する、という背理法です。
の証明では、この論法を全単射の形で厳密に実行します。
最適部分構造は自明に成り立つ性質ではありません。壊れる例を見ておくと、何が効いているのかがはっきりします。
無向グラフ $G$ を、頂点集合 $\{u, v, w, x\}$、辺集合 $\{uv,\ vw,\ wx,\ xu,\ uw\}$ で定めます。単純道とは同じ頂点を 2 度通らない道のことで、$L(a, b)$ を $a$ から $b$ への単純道の辺数の最大値とします。
フィボナッチと同じ発想で「最後の辺で場合分け」すれば、$L(u, w) = \max\{L(u, t) + 1 : t \text{ は } w \text{ の隣接点}\}$ という漸化式を書きたくなります。しかしこれは成り立ちません。実際に両辺を計算します。
まず左辺です。$u$ から $w$ への単純道を列挙します。$u \to w$（1 辺）、$u \to v \to w$（2 辺）、$u \to x \to w$（2 辺）。3 辺の単純道はありません：$u \to v \to ? \to w$ の形にするには $v$ の隣接点が $u, w$ しかないので不可能、$u \to x \to ? \to w$ も $x$ の隣接点が $u, w$ だけなので不可能です。よって $L(u, w) = 2$ です。
次に右辺の一項を計算します。$w$ の隣接点 $v$ について、$u$ から $v$ への単純道は $u \to v$（1 辺）、$u \to w \to v$（2 辺）、$u \to x \to w \to v$（3 辺）で、$L(u, v) = 3$ です。したがって右辺は $L(u, v) + 1 = 4$ 以上になり、左辺の $2$ と一致しません。
破綻の理由は具体的です。$L(u,v)$ を達成する道 $u \to x \to w \to v$ に辺 $vw$ を足すと $u \to x \to w \to v \to w$ となり、$w$ を 2 度通るので単純道になりません。部分問題の最適解が、上位の問題では**実行可能ですらない**のです。原因は、部分問題「$u$ から $v$ への最長単純道」が「これまでどの頂点を使ったか」という情報を捨ててしまっていることにあります。部分問題が状態を十分に表現していないわけです。
なお、最長単純道問題は NP 困難（
## 6. 0-1 ナップサック問題
$n \in \mathbb{Z}_{\ge 1}$、重さ $w_1, \ldots, w_n \in \mathbb{Z}_{\ge 1}$、価値 $v_1, \ldots, v_n \in \mathbb{R}_{\ge 0}$、容量 $W \in \mathbb{Z}_{\ge 0}$ が与えられる。部分集合 $S \subseteq [n]$ が**実行可能**であるとは $w(S) = \sum_{i \in S} w_i \le W$ が成り立つことをいう。実行可能な $S$ のうち $v(S) = \sum_{i \in S} v_i$ を最大にするものを求めよ、というのが 0-1 ナップサック問題である。
「0-1」は各品物を入れるか入れないか（0 個か 1 個か）の二択である、という意味です。素朴には $2^n$ 通りの部分集合を全部試せば解けますが、$n = 60$ で $2^{60} \approx 1.15 \times 10^{18}$ 通りとなり現実的ではありません。
部分問題の設計が勝負です。「品物 $1, \ldots, i$ までしか使えず、容量が $j$ しかない」という制限つきの問題を考えます。
$$
K(i, j) = \max\bigl\{\, v(S) \ :\ S \subseteq [i],\ w(S) \le j \,\bigr\} \qquad (0 \le i \le n,\ 0 \le j \le W)
$$
この最大値は必ず存在します。集合 $\mathcal{F}(i,j) = \{S \subseteq [i] : w(S) \le j\}$ は $\emptyset$ を含むので空でなく、$2^{[i]}$ の部分集合なので有限だからです。求めたい答えは $K(n, W)$ です。
### 6.1. 計算量と実装
```python
def knapsack(w, v, W):
"""w[i], v[i] は 0-indexed。最適値と、選んだ品物の 1-indexed 番号を返す。"""
n = len(w)
K = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(W + 1):
K[i][j] = K[i - 1][j] # 品物 i を入れない
if j >= w[i - 1]: # 入れられるなら比較する
K[i][j] = max(K[i][j], v[i - 1] + K[i - 1][j - w[i - 1]])
chosen, j = [], W # 解の復元
for i in range(n, 0, -1):
if K[i][j] != K[i - 1][j]:
chosen.append(i)
j -= w[i - 1]
chosen.reverse()
return K[n][W], chosen
```
**解の復元が正しい理由。** 最適「値」だけでなく最適「解」が欲しいことがほとんどです。上のコードは表を右下から左上へ辿って選んだ品物を復元しています。その正当性を確かめます。
まず
の 2 と 3 のどちらでも $K(i,j) \ge K(i-1,j)$ です。したがって $K(i,j) \ne K(i-1,j)$ ならば $K(i,j) > K(i-1,j)$ であり、3 の $\max$ は第 2 項で達成されています。つまり $j \ge w_i$ かつ $K(i,j) = v_i + K(i-1, j-w_i)$ です。このとき、$(i-1, j-w_i)$ の最適解 $T$ をとると、証明中の写像 $\Psi$ により $T \cup \{i\}$ は $(i,j)$ の実行可能解で、その価値は $v_i + v(T) = v_i + K(i-1,j-w_i) = K(i,j)$、すなわち最適解です。よって「品物 $i$ を選び、$(i-1, j-w_i)$ へ移る」という手続きは最適性を保ちます。
逆に $K(i,j) = K(i-1,j)$ のときは、$(i-1,j)$ の最適解がそのまま $(i,j)$ の最適解になります（$\mathcal{A} \subseteq \mathcal{F}(i,j)$ なので実行可能で、価値が $K(i,j)$ に等しいからです）。よって「品物 $i$ を選ばず $(i-1, j)$ へ移る」も最適性を保ちます。$i$ が $n$ から $0$ まで減るので手続きは必ず停止し、停止時に集めた集合は $(n,W)$ の最適解です。復元にかかる時間は $O(n)$ です。
品物 4 個、容量 $W = 7$ の例です。
| 品物 $i$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重さ $w_i$ | 1 | 3 | 4 | 5 |
| 価値 $v_i$ | 1 | 4 | 5 | 7 |
行 $0$ は
### 6.2. 領域を 1 次元に落とす
表は $(n+1)(W+1)$ マスありますが、
の右辺に現れるのは行 $i-1$ だけです。したがって 1 行分の配列を使い回せます。ただし更新の順序に注意が要ります。
長さ $W+1$ の配列 $\kappa$ を $\kappa[j] = 0$（$0 \le j \le W$）で初期化し、$i = 1, 2, \ldots, n$ の順に、各 $i$ について $j$ を $W$ から $w_i$ まで**降順**に動かして
$$
\kappa[j] \leftarrow \max\bigl\{ \kappa[j],\ v_i + \kappa[j - w_i] \bigr\}
$$
と更新する。このとき、$i$ 回目のループを終えた時点で、すべての $0 \le j \le W$ について $\kappa[j] = K(i, j)$ が成り立つ。とくに全体を終えると $\kappa[W] = K(n, W)$ である。
$i$ に関する帰納法です。$i = 0$（ループ開始前）では $\kappa[j] = 0 = K(0,j)$ が
```python
def knapsack_value(w, v, W):
kappa = [0] * (W + 1)
for wi, vi in zip(w, v):
for j in range(W, wi - 1, -1): # 降順が本質的
kappa[j] = max(kappa[j], vi + kappa[j - wi])
return kappa[W]
```
### 6.3. 擬多項式時間という落とし穴
は嬉しい結果ですが、注意が要ります。計算量は**入力のサイズ**の関数として測るのが約束でした（[計算量と O 記法](/computer-science/algorithms/complexity-and-big-o)、
）。ナップサック問題の入力を 2 進表記で書き下すと、その長さは $\Theta\bigl(\sum_i (\log w_i + \log v_i) + \log W\bigr)$ 程度です。容量 $W$ は $\log W$ ビットで書けてしまいます。
つまり、入力長を $L$ とすると $W$ は $2^{L}$ 程度まで大きくなり得ます。$n = 100$、$W = 2^{60}$ という入力は 2 進表記で数百ビットしかありませんが、$O(nW)$ の表は $10^{20}$ マスを超えます。このように「数値そのもの」に対して多項式で、入力の**ビット長**に対しては指数的な計算量を**擬多項式時間**といいます。
0-1 ナップサック問題は NP 困難です。ですから、$\mathrm{P} \ne \mathrm{NP}$ ならば真の多項式時間アルゴリズム（
）は存在しません（[P≠NP予想とは何か](/computer-science/algorithms/p-vs-np)）。動的計画法は万能の魔法ではなく、「数値が小さいときに限って指数の壁を回避できる」道具なのだ、と理解してください。
## 7. 設計の手順と、もう一つの例
ここまでの例から、動的計画法の設計手順を取り出せます。
1. **部分問題を決める。** 何を添字にするか。
が示すように、添字は「上位の問題を解くのに必要な情報をすべて含む」必要があります。
2. **漸化式を立てる。** 最適解の「最後の一手」で場合分けするのが定石です。ナップサックでは「品物 $i$ を入れたか」でした。
3. **基底を決める。** 添字が最小のところで、直接値が定まるようにします。
4. **順序と復元を決める。** 依存グラフの位相順序でループを書き、必要なら解を復元する情報を残します。
この手順を、文字列の比較に使う編集距離に当てはめます。
有限アルファベット上の文字列 $x$、$y$ に対し、次の 3 種の操作をそれぞれコスト $1$ として、$x$ を $y$ に変換する操作列のうちコストの総和が最小のものの値を**編集距離** $d(x,y)$ と呼ぶ。
- 1 文字の削除
- 1 文字の挿入
- 1 文字を別の 1 文字に置換
証明にはアライメントによる言い換えを使います。$x$ と $y$ の**アライメント**とは、両者にギャップ記号を挿入して長さを揃え、上下 2 段に並べた表のことです。すなわち列 $(a_1,b_1), \ldots, (a_\ell, b_\ell)$ であって、$a_t$ からギャップを除くと $x$ に、$b_t$ からギャップを除くと $y$ になり、$(a_t, b_t)$ が両方ギャップである列は含まないもののことです。列 $(a_t,b_t)$ のコストを $a_t = b_t$ のとき $0$、それ以外のとき $1$ と定め、アライメントのコストを列ごとのコストの和とします。
このとき、「$x$ を $y$ に変換する操作列の最小コスト」と「$x$ と $y$ のアライメントの最小コスト」は一致します。証明は Wagner と Fischer の論文、あるいは Gusfield の教科書第 11 章にあります。以下ではこの特徴づけを既知として使います。
$x = x_1 x_2 \cdots x_m$、$y = y_1 y_2 \cdots y_n$ を有限アルファベット上の文字列とし、$0 \le i \le m$、$0 \le j \le n$ に対して $D(i,j) = d(x_1 \cdots x_i,\ y_1 \cdots y_j)$ とおく（$i = 0$ や $j = 0$ のときは空文字列とする）。このとき
$$
D(i, 0) = i \quad (0 \le i \le m), \qquad D(0, j) = j \quad (0 \le j \le n)
$$
であり、$1 \le i \le m$、$1 \le j \le n$ に対して
$$
D(i,j) = \min\bigl\{\, D(i-1, j) + 1,\ \ D(i, j-1) + 1,\ \ D(i-1,j-1) + [\, x_i \ne y_j \,] \,\bigr\}
$$
が成り立つ。ここで $[\,x_i \ne y_j\,]$ は $x_i \ne y_j$ のとき $1$、$x_i = y_j$ のとき $0$ を表す。
依存グラフの辺は $(i-1,j)$、$(i,j-1)$、$(i-1,j-1)$ から $(i,j)$ へ向かい、辺を辿るたびに $i + j$ が必ず増えるので閉路はありません。部分問題は $(m+1)(n+1)$ 個、遷移は $O(1)$ なので、
より計算時間は $O(mn)$、領域は $O(mn)$ です（1 行ずつ捨てれば $O(\min\{m,n\})$ にできます）。
$x = \texttt{kitten}$（$m=6$）、$y = \texttt{sitting}$（$n=7$）の表を埋めます。第 0 行と第 0 列は基底の $D(0,j) = j$、$D(i,0) = i$ です。
| | $\varepsilon$ | s | i | t | t | i | n | g |
|---|---|---|---|---|---|---|---|---|
| $\varepsilon$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| **k** | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| **i** | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| **t** | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| **t** | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| **e** | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| **n** | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
たとえば $D(1,1)$ は $x_1 = \texttt{k}$、$y_1 = \texttt{s}$ で異なるので $\min\{D(0,1)+1,\ D(1,0)+1,\ D(0,0)+1\} = \min\{2, 2, 1\} = 1$ です。$D(2,2)$ は $x_2 = y_2 = \texttt{i}$ なので $\min\{D(1,2)+1,\ D(2,1)+1,\ D(1,1)+0\} = \min\{3, 3, 1\} = 1$ です。
答えは $D(6,7) = 3$。実際、$\texttt{kitten} \to \texttt{sitten}$（k を s に置換）$\to \texttt{sittin}$（e を i に置換）$\to \texttt{sitting}$（g を挿入）で 3 手です。表が $3$ を返し、かつ 3 手の変換が実在するので、これが最小です。
## 8. 演習
## 参考文献
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, *Introduction to Algorithms*, 4th ed., MIT Press, 2022 — 第 14 章「Dynamic Programming」（第 3 版では第 15 章）。ロッド切断問題から始めて最適部分構造と部分問題の重複を丁寧に扱っています。
- J. Kleinberg, É. Tardos, *Algorithm Design*, Addison-Wesley, 2005 — 第 6 章「Dynamic Programming」。§6.4 でナップサック問題、§11.8 でその近似解法（FPTAS）を扱っています。
- R. Bellman, *Dynamic Programming*, Princeton University Press, 1957 — 動的計画法の原典。最適性原理の定式化があります。
- R. Bellman, *Eye of the Hurricane: An Autobiography*, World Scientific, 1984 — 「dynamic programming」という名称の由来についての本人の回想。
- R. A. Wagner, M. J. Fischer, "The string-to-string correction problem", *Journal of the ACM* 21 (1974), 168–173 — 編集距離の $O(mn)$ アルゴリズムと、その正しさの証明。
- D. Gusfield, *Algorithms on Strings, Trees, and Sequences*, Cambridge University Press, 1997 — 第 11 章。編集距離、アライメント、動的計画法の関係を体系的に扱っています。
## Appendix: 同じ問題に対する別の動的計画法
**価値を添字にする。**
のナップサック問題で、価値 $v_i$ がすべて非負整数だとします。
の $O(nW)$ は $W$ が大きいと使えませんが、添字の役割を入れ替えると別の計算量が得られます。
$$
M(i, p) = \min\bigl\{\, w(S) \ :\ S \subseteq [i],\ v(S) = p \,\bigr\}
$$
を「品物 $1,\ldots,i$ から選んで価値がちょうど $p$ になる部分集合の最小の重さ」と定めます（そのような $S$ がなければ $+\infty$）。基底は $M(0,0) = 0$ と $M(0,p) = +\infty$（$p \ge 1$）です。
とまったく同じ全単射の議論により、$p \ge v_i$ のとき
$$
M(i,p) = \min\bigl\{\, M(i-1, p),\ \ w_i + M(i-1,\ p - v_i) \,\bigr\}
$$
が、$p < v_i$ のとき $M(i,p) = M(i-1,p)$ が成り立ちます。求める最適値は $\max\{p : M(n,p) \le W\}$ です。$V = \sum_{i} v_i$ とおくと部分問題は $(n+1)(V+1)$ 個なので、
より $O(nV)$ 時間です。
の例では $V = 1 + 4 + 5 + 7 = 17$ なので $O(4 \cdot 18)$、この場合は $O(nW)$ 版と大差ありませんが、$W$ が巨大で価値が小さい入力ではこちらが圧倒的に速くなります。逆に価値が巨大なら $O(nW)$ 版を使います。**同じ問題に対して複数の部分問題の切り方があり、入力の性質で使い分ける**というのは、動的計画法では珍しくありません。
**近似への入り口。** $O(nV)$ という形は、価値を適当な単位で丸めて $V$ を小さくすれば計算が速くなることを示唆します。丸めによる誤差を制御すると、任意の $\varepsilon > 0$ に対して最適値の $(1-\varepsilon)$ 倍以上の解を多項式時間で返すアルゴリズム（FPTAS）が構成できます。詳しくは Kleinberg–Tardos の §11.8 を参照してください。NP 困難性が「厳密解の多項式時間計算」を阻んでも、近似ならこの壁を越えられることがあります。