動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える

0. この記事の要点

• 動的計画法は「問題を部分問題に分ける」技法ではありません。分割統治もそれをします。本質は、分けた部分問題が重複して現れるときに、答えを表に記録して一度しか解かないことです。
• 部分問題の依存関係が有向非巡回グラフ（DAG）になっていれば、位相順に解けます。全体の計算時間は「部分問題の個数 × 1 つあたりの遷移コスト」で見積もれます（Theorem 3.2）。この 1 本の定理で、以下のすべての計算量が出ます。
• フィボナッチ数を定義どおりの再帰で計算すると、関数呼び出しの総数はちょうど $2F_{n+1} - 1$ 回、すなわち $\Theta(\varphi^n)$ 回です。表を使えば $O(n)$ 回の加算で済みます。
• 動的計画法が使えるかどうかは最適部分構造が成り立つかで決まります。成り立たない例（最長単純道）を見れば、どこで壊れるのかがはっきりします。
• 0-1 ナップサック問題は $O(nW)$ の表計算で最適値と最適解の両方が求まります。ただしこれは入力のビット長に対する多項式時間ではありません（擬多項式時間）。この差は本質的で、ナップサック問題自体は NP 困難です。

1. 動機：同じ部分問題を何度も解いていないか

再帰は、問題を小さな同種の問題に分解する強力な道具です。マージソートは長さ $n$ の列を長さ $\lfloor n/2 \rfloor$ と $\lceil n/2 \rceil$ の 2 つに分け、それぞれを整列してから併合しました（ソートアルゴリズム、Theorem 4.2［Sorting Algorithms］）。ここで見落としやすい前提があります。分割された 2 つの部分列は互いに交わらない、つまり左半分を整列する仕事と右半分を整列する仕事はまったく別物だ、ということです。

ところが、同じ形で書いた再帰が破滅的に遅くなることがあります。フィボナッチ数 $F_0 = 0$、$F_1 = 1$、$F_n = F_{n-1} + F_{n-2}$ $(n \ge 2)$ の定義をそのまま Python に写してみます。

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

このコードは正しく動きます。しかし fib_naive(40) は普通の計算機で数秒かかり、fib_naive(50) は分単位になります。$n$ を 1 増やすごとに時間がおよそ 1.6 倍、10 増やすと約 123 倍です。理由は、呼び出しの木を描けばすぐに見えます。

flowchart TD
a5["F(5)"] --> a4["F(4)"]
a5 --> b3["F(3)"]
a4 --> a3["F(3)"]
a4 --> b2["F(2)"]
b3 --> c2["F(2)"]
b3 --> d1["F(1)"]
a3 --> e2["F(2)"]
a3 --> f1["F(1)"]
b2 --> g1["F(1)"]
b2 --> h0["F(0)"]
c2 --> i1["F(1)"]
c2 --> j0["F(0)"]
e2 --> k1["F(1)"]
e2 --> l0["F(0)"]

fib_naive(5) の呼び出し木。F(3) は 2 回、F(2) は 3 回、F(1) は 5 回、それぞれ独立に計算されている

$F(3)$ を計算する部分木が、まるごと 2 回現れています。$F(2)$ は 3 回です。$n$ を大きくすればこの重複は指数的に膨れ上がります。一方で、私たちが本当に知る必要のある値は $F_0, F_1, \ldots, F_n$ の $n+1$ 個しかありません。一度計算した答えを書き留めて使い回す——これが動的計画法のすべてです。

アイデア自体は素朴です。しかしそれだけでは、次の 3 つの問いに答えられません。

1. 使い回してよいのはなぜか。部分問題の答えは、それを呼び出した文脈に依存しないのか。
2. どんな問題で使えるのか。使えない問題との境目はどこか。
3. どれだけ速くなるのか。速さは何で決まるのか。

この記事はこの 3 つに順に答えます。なお「動的計画法（dynamic programming）」という名前は 1950 年代に Richard Bellman が付けたものです。彼は自伝のなかで、当時の国防長官が「研究」という語を嫌ったため、数学的な色を消しつつ印象のよい語を選んだ、という趣旨のことを書いています。名前から意味を読み取ろうとしても徒労で、ここでの programming は「表を作る計画」ほどの意味であり、プログラミング言語とは関係ありません。

2. 準備：計算モデルと記号

計算量は単位費用 RAM モデル（Definition 2.1［Complexity and Big-O Notation］）で数えます。加減算・比較・配列の添字アクセスを 1 ステップとします。$O$ 記法については 計算量と O 記法 を、配列が添字アクセスを $O(1)$ でできることについては 基本的なデータ構造（Proposition 3.2［Fundamental Data Structures］）を前提とします。有向非巡回グラフ（DAG）と位相ソートは グラフアルゴリズム（DAG であることの特徴づけは Theorem 4.2［グラフアルゴリズム］）の内容を使います。

記号を決めておきます。

• $[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$ です。

Note

単位費用モデルは「扱う数が機械語 1 語に収まる」という仮定の上に成り立っています。フィボナッチ数のように値そのものが指数的に大きくなる場合、この仮定は破れます。Remark 4.4 で改めて触れます。

3. 動的計画法の枠組み

まず、動的計画法という手法を一般的な形で書き下します。個々の問題ごとに計算量を数え直さずに済むようにするためです。

Definition 3.1（部分問題族と依存グラフ）

有限集合 $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$ の位相順序に沿って計算すれば、必要な値は必ず先に手に入っています。この観察をそのまま定理にしたのが次です。

Theorem 3.2（動的計画法の計算量）

Definition 3.1 の意味の部分問題族 $(S, D, g)$ が与えられ、$N = |S|$ とする。表への読み書きが $1$ ステップででき、各 $s$ について、依存先の値 $V(s_1), \ldots, V(s_{k_s})$ がすでに表にあるという条件のもとで $g_s$ の評価が $c(s)$ ステップでできるとする。このとき、すべての $s \in S$ に対する $V(s)$ を

$$O\Bigl(N + \sum_{s \in S} c(s)\Bigr)$$

ステップ、$O(N)$ の作業領域で計算できる。とくに、ある定数 $c$ が存在してすべての $s \in S$ で $c(s) \le c$ ならば、計算時間は $O(Nc)$ である。

Proof（Theorem 3.2）

$G = (S, E)$ を Definition 3.1 の条件 3 の DAG とします。

第 1 段：位相順序をとる。 条件 3 より $G$ は DAG なので、位相順序、すなわち $S$ の全体の並べ替え $s^{(1)}, s^{(2)}, \ldots, s^{(N)}$ で、$(s^{(p)}, s^{(q)}) \in E$ ならば必ず $p < q$ となるものが存在します（グラフアルゴリズム）。その計算には $O(N + |E|)$ ステップかかります。ここで $|E| = \sum_{s \in S} k_s$ ですが、$g_s$ を評価するには少なくとも $k_s$ 個の引数を読まなければならないので $c(s) \ge k_s$ であり、したがって $|E| \le \sum_{s} c(s)$ です。つまり位相ソートの費用は主張の $O(N + \sum_s c(s))$ に収まります。

第 2 段：位相順に埋める。 大きさ $N$ の表 $T$ を用意し（確保と初期化に $O(N)$）、$q = 1, 2, \ldots, N$ の順に $T[s^{(q)}] \leftarrow g_{s^{(q)}}\bigl(T[s_1], \ldots, T[s_{k}]\bigr)$ と代入します（$D(s^{(q)}) = (s_1, \ldots, s_k)$）。

この代入が正しく実行できることを確認します。$s_i \in D(s^{(q)})$ なら $(s_i, s^{(q)}) \in E$ ですから、位相順序の定義により $s_i$ は $s^{(q)}$ より前に並んでいます。よって $T[s_i]$ にはすでに値が入っています。さらに $q$ に関する帰納法により、その値は $V(s_i)$ に等しい：$q = 1$ のとき $s^{(1)}$ は依存先をもてない（もてば依存先が $s^{(1)}$ より前に来て矛盾）ので基底であり、$T[s^{(1)}] = g_{s^{(1)}}() = V(s^{(1)})$。$q$ 未満で成立を仮定すれば、$T[s_i] = V(s_i)$ なので条件 2 より $T[s^{(q)}] = g_{s^{(q)}}(V(s_1), \ldots, V(s_k)) = V(s^{(q)})$ です。

第 3 段：費用を数える。 各 $q$ での代入は仮定より $c(s^{(q)})$ ステップです。総和は $\sum_{s \in S} c(s)$。これに第 1 段と表の初期化の $O(N + \sum_s c(s))$ を足しても主張の範囲です。領域は表の $O(N)$ に、位相ソートの作業領域 $O(N)$ を足して $O(N)$ です。

最後の主張は、$c(s) \le c$ なら $\sum_s c(s) \le Nc$ であり、また $c \ge 1$ としてよいので $N + Nc = O(Nc)$ となることから従います。

∎

この定理の使い方は決まっています。部分問題を何個作ったか（$N$）と、1 つの部分問題を解くのに何ステップかかるか（$c$）を数える。掛ければ計算量が出る。 以降のフィボナッチ、ナップサック、編集距離の計算量は、すべてこの一言で片づきます。

3.1. トップダウンとボトムアップ

Theorem 3.2 の証明では位相順序を先に求めましたが、実装では 2 つの流儀があります。

Proposition 3.3（メモ化再帰の計算量）

Definition 3.1 の設定のもとで、次の再帰手続き $\mathrm{solve}(s)$ を考える。

• 表 $T[s]$ が「未計算」でなければ $T[s]$ を返す。
• そうでなければ、$D(s) = (s_1, \ldots, s_k)$ の各要素に対して $\mathrm{solve}(s_i)$ を呼び、その結果に $g_s$ を適用した値を $T[s]$ に書き込んで返す。

このとき、$s_0 \in S$ から $G$ の辺を逆向きに辿って到達できる部分問題の集合を $R \subseteq S$（$s_0 \in R$）とすると、$\mathrm{solve}(s_0)$ は停止し、$V(s_0)$ を返す。その計算時間は $O\bigl(|R| + \sum_{s \in R} c(s)\bigr)$ であり、$R$ に属さない部分問題は一度も評価されない。

Proof（Proposition 3.3）

停止性と正しさ。 $G$ は DAG なので、$s$ から辺を逆向きに辿る道の長さの最大値 $h(s)$（$s$ の依存の深さ）が有限に定まります。閉路があればこれは定義できませんから、ここで条件 3 を使っています。$h(s)$ に関する帰納法で示します。$h(s) = 0$ なら $D(s)$ は空、つまり $s$ は基底なので、$\mathrm{solve}(s)$ は再帰せずに $g_s() = V(s)$ を返して停止します。$h(s) = d > 0$ とすると、各 $s_i \in D(s)$ は $h(s_i) \le d - 1$ を満たすので、帰納法の仮定より $\mathrm{solve}(s_i)$ は停止して $V(s_i)$ を返します。よって $\mathrm{solve}(s)$ は停止し、条件 2 より $g_s(V(s_1), \ldots, V(s_k)) = V(s)$ を返します。

各部分問題の本体は高々 1 回しか実行されない。 $s$ の本体（再帰呼び出しと $g_s$ の評価）が実行し終わると $T[s]$ に値が書き込まれ、以後「未計算」ではなくなります。したがって 2 回目以降の $\mathrm{solve}(s)$ は最初の分岐で戻ります。本体が実行されるのは最初の 1 回だけです。

呼び出し回数。 本体が実行される $s$ は $R$ の元だけです（$s_0$ から到達不能な部分問題は呼ばれません）。本体 1 回につき再帰呼び出しは $|D(s)| = k_s$ 回起きるので、$\mathrm{solve}$ の総呼び出し回数は $1 + \sum_{s \in R} k_s$ です。Theorem 3.2 の証明と同じ理由で $k_s \le c(s)$ ですから、呼び出しのオーバーヘッド（$1$ 回あたり $O(1)$）の総和は $O(|R| + \sum_{s \in R} c(s))$ に収まります。本体での $g_s$ の評価は合計 $\sum_{s \in R} c(s)$ ステップです。

∎

2 つの流儀を比べます。

	メモ化再帰（トップダウン）	表計算（ボトムアップ）
計算順序	再帰が依存関係を自動的に辿る	位相順を人が決めてループに書く
実際に解く部分問題	必要なものだけ（Proposition 3.3 の $R$）	表の全マス
実装	素朴な再帰に表を足すだけ	ループの順序を設計する必要がある
弱点	再帰の深さ制限、呼び出しのオーバーヘッド	使わない部分問題も解いてしまう
領域の削減	しにくい	「直前の行だけ持つ」等がやりやすい

どちらも Theorem 3.2 と同じオーダーの計算量になります。以下では両方を使い分けます。

4. フィボナッチ数列：指数時間から線形時間へ

§1 で観察した重複を、まず定量化します。

Proposition 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)$ である。

Proof（Proposition 4.1）

等式。 $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$ ではどうなるかは Exercise 8.1 で計算してもらいます。

4.1. 表を持てば線形になる

Definition 3.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 の条件も満たされます。

Corollary 4.2（フィボナッチ数の線形時間計算）

上の部分問題族に Theorem 3.2 を適用すると、$F_0, F_1, \ldots, F_n$ のすべてが $O(n)$ ステップ、$O(n)$ の領域で計算できる。$F_n$ だけが必要なら領域は $O(1)$ でよい。

Proof（Corollary 4.2）

部分問題の個数は $N = n + 1$ です。遷移 $g_k$ は表引き 2 回と加算 1 回なので $c(k) = O(1)$、すなわち定数 $c$ で上から押さえられます。Theorem 3.2 より計算時間は $O(Nc) = O(n)$、領域は $O(N) = O(n)$ です。

領域についての後半を示します。位相順序は $0, 1, 2, \ldots, n$ ととれ、$k$ の計算に必要なのは $k-1$ と $k-2$ の値だけです。よって直前 2 つの値を変数 2 個に保持し、$k$ を 1 つ進めるごとに更新すれば、表全体を保持する必要はありません。使う記憶は変数 2 個と添字 1 個で $O(1)$ です。

∎

トップダウン（メモ化再帰）とボトムアップ（反復）の両方を書いておきます。

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 行足しただけです。それでも Proposition 3.3 より、実際に本体が実行される部分問題は $R = \{0, 1, \ldots, n\}$ の $n+1$ 個だけになります。

Example 4.3（n = 10 での比較）

$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 個です。一方、素朴な再帰の呼び出し回数は Proposition 4.1 より $T(10) = 2F_{11} - 1 = 2 \cdot 89 - 1 = 177$ 回でした。$n = 10$ ですでに 16 倍の差がついています。$n = 30$ では $T(30) = 2F_{31} - 1 = 2{,}692{,}537$ 回に対し、表は 31 マスです。

Remark 4.4（単位費用モデルの限界）

Corollary 4.2 の $O(n)$ は「1 回の加算が $O(1)$」という単位費用モデルの下での値です。しかし Proposition 4.1 の証明で示した $F_m \ge \varphi^{m-2}$ より、$F_n$ の 2 進表記は $\Theta(n)$ ビットあります。多倍長整数として扱えば 1 回の加算は $\Theta(n)$ ビット演算なので、ビット演算で数えた計算量は $\Theta(n^2)$ です。それでも指数から多項式への改善は本物です。

なお、$F_n$ だけが欲しいなら、行列の等式

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}$$

を繰り返し二乗法で計算して、乗算 $O(\log n)$ 回に減らせます。これは動的計画法ではなく、問題固有の代数構造を使う別の技法です。動的計画法は「構造が見つからないときにも使える汎用の道具」だと考えてください。

5. 最適部分構造：使える条件と、壊れる例

フィボナッチ数は「値を計算する」問題でした。動的計画法が本領を発揮するのは最適化問題ですが、そこには追加の条件が要ります。

Definition 5.1（最適部分構造）

最適化問題の族 $\{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$ の最適性に反する、という背理法です。Theorem 6.2 の証明では、この論法を全単射の形で厳密に実行します。

最適部分構造は自明に成り立つ性質ではありません。壊れる例を見ておくと、何が効いているのかがはっきりします。

Example 5.2（最長単純道では最適部分構造が壊れる）

無向グラフ $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 困難（Definition 6.1［P≠NP 予想とは何か］）であることが知られています（P≠NP予想とは何か）。安直な動的計画法が効かないのには理由がある、ということです。

6. 0-1 ナップサック問題

Definition 6.1（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)$ です。

Theorem 6.2（ナップサック問題の漸化式）

Definition 6.1 の設定のもとで、上の $K(i,j)$ について次が成り立つ。

1. すべての $0 \le j \le W$ に対し $K(0, j) = 0$。
2. $1 \le i \le n$ かつ $0 \le j < w_i$ のとき $K(i, j) = K(i-1, j)$。
3. $1 \le i \le n$ かつ $w_i \le j \le W$ のとき

$$K(i, j) = \max\bigl\{\, K(i-1, j),\ \ v_i + K(i-1,\ j - w_i) \,\bigr\}.$$

Proof（Theorem 6.2）

1 の証明。 $S \subseteq [0] = \emptyset$ なる $S$ は $S = \emptyset$ のみで、$w(\emptyset) = 0 \le j$ より実行可能、$v(\emptyset) = 0$ です。したがって最大値は $0$ です。

2 の証明。 $j < w_i$ とします。$S \in \mathcal{F}(i,j)$ が $i \in S$ を満たすと仮定すると、重さはすべて正（Definition 6.1 で $w_k \in \mathbb{Z}_{\ge 1}$ としました）なので $w(S) \ge w_i > j$ となり、$w(S) \le j$ に矛盾します。よって $\mathcal{F}(i,j)$ の元はすべて $i$ を含まず、$S \subseteq [i] \setminus \{i\} = [i-1]$ です。逆に $\mathcal{F}(i-1,j)$ の元は $\mathcal{F}(i,j)$ の元でもあります。つまり $\mathcal{F}(i,j) = \mathcal{F}(i-1,j)$ であり、同じ集合上で同じ関数 $v$ を最大化するので $K(i,j) = K(i-1,j)$ です。

3 の証明。 $w_i \le j$ とします。$\mathcal{F}(i,j)$ を、$i$ を含まないもの全体 $\mathcal{A}$ と、$i$ を含むもの全体 $\mathcal{B}$ に分割します。$\mathcal{F}(i,j) = \mathcal{A} \sqcup \mathcal{B}$ です。

$\mathcal{A}$ について。2 の証明と同じ議論で $\mathcal{A} = \mathcal{F}(i-1, j)$ です。よって $\max_{S \in \mathcal{A}} v(S) = K(i-1, j)$。

$\mathcal{B}$ について。写像 $\Phi : \mathcal{B} \to \mathcal{F}(i-1, j-w_i)$、$\Phi(S) = S \setminus \{i\}$ が全単射であることを示します。

• 行き先が正しい： $S \in \mathcal{B}$ なら $S \setminus \{i\} \subseteq [i-1]$ であり、$w(S \setminus \{i\}) = w(S) - w_i \le j - w_i$ です（$i \in S$ を使いました）。よって $\Phi(S) \in \mathcal{F}(i-1, j-w_i)$。
• 逆写像がある： $\Psi(T) = T \cup \{i\}$ とおきます。$T \in \mathcal{F}(i-1, j-w_i)$ なら $T \subseteq [i-1]$ より $i \notin T$ なので $w(T \cup \{i\}) = w(T) + w_i \le (j - w_i) + w_i = j$ であり、$T \cup \{i\} \subseteq [i]$ かつ $i$ を含むので $\Psi(T) \in \mathcal{B}$ です。$i \notin T$ から $\Phi(\Psi(T)) = T$、$i \in S$ から $\Psi(\Phi(S)) = S$ が従い、$\Phi$ は全単射です。

さらに、$i \in S$ より $v(S) = v_i + v(S \setminus \{i\}) = v_i + v(\Phi(S))$ です。$\Phi$ が全単射なので

$$\max_{S \in \mathcal{B}} v(S) = \max_{T \in \mathcal{F}(i-1,\, j-w_i)} \bigl(v_i + v(T)\bigr) = v_i + K(i-1,\ j-w_i)$$

が成り立ちます。ここで $\mathcal{F}(i-1, j-w_i)$ は $\emptyset$ を含むので空でなく（$j - w_i \ge 0$ を使いました）、右辺の最大値は存在します。また $\{i\} \in \mathcal{B}$ なので $\mathcal{B} \ne \emptyset$、$\emptyset \in \mathcal{A}$ なので $\mathcal{A} \ne \emptyset$ です。

空でない 2 つの有限集合の合併上の最大値は、それぞれの最大値の大きい方に等しいので、

$$K(i,j) = \max\Bigl\{ \max_{S \in \mathcal{A}} v(S),\ \max_{S \in \mathcal{B}} v(S) \Bigr\} = \max\bigl\{ K(i-1,j),\ v_i + K(i-1, j-w_i) \bigr\}$$

となり、3 が示されました。

∎

Remark 6.3（どの仮定をどこで使ったか）

証明を振り返ると、$w_i \ge 1$（正であること）は 2 の場合分けだけで使い、$w_i, W$ が整数であることは実は上の証明では使っていません。整数性は、次に見るように表の添字を $j = 0, 1, \ldots, W$ と有限個に限るために必要になります。$w_i$ が実数だと、あり得る残り容量が連続無限個になって表が作れません。

また、価値 $v_i \ge 0$ という仮定も証明のどこでも使っていません。$v_i$ が負の実数でも Theorem 6.2 はそのまま成り立ちます（負の価値の品物は最適解に入らないだけです）。仮定は少ない方が定理は強いので、これは書き留めておく価値があります。

ナップサック表の遷移。セル (i, j) は 1 行上の 2 つのセルだけから決まる

6.1. 計算量と実装

Corollary 6.4（ナップサック問題の計算量）

Definition 6.1 の 0-1 ナップサック問題の最適値 $K(n, W)$ は $O(nW)$ ステップ、$O(nW)$ の領域で計算できる。

Proof（Corollary 6.4）

部分問題の添字集合を $S = \{(i,j) : 0 \le i \le n,\ 0 \le j \le W\}$、値を $V(i,j) = K(i,j)$ とします。Theorem 6.2 より、依存先は $D(0,j) = ()$、$j < w_i$ のとき $D(i,j) = ((i-1, j))$、$j \ge w_i$ のとき $D(i,j) = ((i-1,j),\ (i-1, j-w_i))$ ととれます。ここで $w_i$ と $W$ が整数（Definition 6.1）なので $j - w_i$ も整数であり、$0 \le j - w_i \le W$ より確かに $S$ の元です。

依存グラフが DAG であることを確認します。辺は必ず第 1 成分が $i-1$ の点から $i$ の点へ向かうので、辺を辿るたびに第 1 成分が 1 ずつ増えます。閉路があれば第 1 成分が元に戻らねばならず、矛盾です。よって Definition 3.1 の条件がすべて満たされます。

部分問題の個数は $N = (n+1)(W+1)$ です。遷移は表引き高々 2 回、加算 1 回、比較 1 回なので $c(i,j) = O(1)$ です。Theorem 3.2 より計算時間は $O(N) = O((n+1)(W+1)) = O(nW + n + W + 1)$、領域も $O(N)$ です。$n \ge 1$ なので、これは $O(nW + W)$ と書けます。$W = 0$ の場合を別に扱えば（このとき答えは $0$ です）、以後 $W \ge 1$ として $O(nW)$ と書けます。

位相順序としては、$i$ を $0$ から $n$ へ増やし、各 $i$ の中では $j$ を $0$ から $W$ へ動かす順序がとれます。実際、辺 $(i-1, \cdot) \to (i, \cdot)$ は必ず $i$ が増える向きなので、この順序で並べれば依存先は必ず先に来ます。

∎

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

解の復元が正しい理由。 最適「値」だけでなく最適「解」が欲しいことがほとんどです。上のコードは表を右下から左上へ辿って選んだ品物を復元しています。その正当性を確かめます。

まず Theorem 6.2 の 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)$ です。

Example 6.5（表を最後まで埋める）

品物 4 個、容量 $W = 7$ の例です。

品物 $i$	1	2	3	4
重さ $w_i$	1	3	4	5
価値 $v_i$	1	4	5	7

行 $0$ は Theorem 6.2 の 1 より全部 $0$ です。行 $1$（$w_1 = 1$, $v_1 = 1$）は、$j = 0$ では $j < w_1$ なので $K(1,0) = K(0,0) = 0$、$j \ge 1$ では $\max\{0,\ 1 + K(0, j-1)\} = \max\{0, 1\} = 1$ です。

行 $2$（$w_2 = 3$, $v_2 = 4$）を丁寧に計算します。$j = 0,1,2$ では $j < 3$ なので上の行をそのまま写して $0, 1, 1$。$j = 3$ では $\max\{K(1,3),\ 4 + K(1,0)\} = \max\{1, 4+0\} = 4$。$j=4$ では $\max\{1,\ 4 + K(1,1)\} = \max\{1, 5\} = 5$。$j = 5, 6, 7$ では $4 + K(1, j-3) = 4 + 1 = 5$ なので、いずれも $5$ です。

同様に行 $3$（$w_3 = 4$, $v_3 = 5$）と行 $4$（$w_4 = 5$, $v_4 = 7$）を埋めると、表全体は次のようになります。

$i \backslash j$	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	1	1	1	1	1	1	1
2	0	1	1	4	5	5	5	5
3	0	1	1	4	5	6	6	9
4	0	1	1	4	5	7	8	9

たとえば $K(3,7) = \max\{K(2,7),\ 5 + K(2,3)\} = \max\{5,\ 5+4\} = 9$、$K(4,7) = \max\{K(3,7),\ 7 + K(3,2)\} = \max\{9,\ 7+1\} = 9$ です。

復元。 $(i,j) = (4,7)$ から始めます。$K(4,7) = 9 = K(3,7)$ なので品物 4 は選ばず $(3,7)$ へ。$K(3,7) = 9 \ne 5 = K(2,7)$ なので品物 3 を選び、$j$ を $7 - w_3 = 3$ にして $(2,3)$ へ。$K(2,3) = 4 \ne 1 = K(1,3)$ なので品物 2 を選び、$j$ を $3 - w_2 = 0$ にして $(1,0)$ へ。$K(1,0) = 0 = K(0,0)$ なので品物 1 は選びません。

得られた解は $S = \{2, 3\}$ で、重さ $3 + 4 = 7 \le 7$、価値 $4 + 5 = 9$ です。全 16 通りを手で確かめても、価値 $9$ を超える実行可能解はありません（品物 2 と 4 は重さ $8 > 7$、品物 3 と 4 は $9 > 7$ で入りません）。

6.2. 領域を 1 次元に落とす

表は $(n+1)(W+1)$ マスありますが、Theorem 6.2 の右辺に現れるのは行 $i-1$ だけです。したがって 1 行分の配列を使い回せます。ただし更新の順序に注意が要ります。

Proposition 6.6（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)$ である。

Proof（Proposition 6.6）

$i$ に関する帰納法です。$i = 0$（ループ開始前）では $\kappa[j] = 0 = K(0,j)$ が Theorem 6.2 の 1 より成り立ちます。

$i-1$ 回目を終えた時点で $\kappa[j] = K(i-1, j)$（すべての $j$）が成り立つとします。$i$ 回目のループで、添字 $j$ を書き換える瞬間の $\kappa[j]$ と $\kappa[j - w_i]$ の値を調べます。

$w_i \ge 1$ なので $j - w_i < j$ です。このループは $j$ を降順に動かすので、添字 $j - w_i$ の書き換えは添字 $j$ の書き換えより後に起こります。また添字 $j$ 自身はこのループでまだ書き換えられていません。したがって、右辺を評価する時点で $\kappa[j]$ と $\kappa[j-w_i]$ はどちらも $i-1$ 回目終了時の値、すなわち帰納法の仮定より $K(i-1, j)$ と $K(i-1, j-w_i)$ です。よって代入後の値は

$$\max\bigl\{ K(i-1,j),\ v_i + K(i-1, j-w_i) \bigr\} = K(i,j)$$

であり、最後の等号は Theorem 6.2 の 3 です（$j \ge w_i$ の範囲を動かしているので 3 が適用できます）。$j < w_i$ の範囲は書き換えられず $K(i-1,j)$ のままですが、これは Theorem 6.2 の 2 より $K(i,j)$ に等しい値です。以上ですべての $j$ で $\kappa[j] = K(i,j)$ となりました。

∎

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]

Caution

range(W, wi - 1, -1) を range(wi, W + 1) に書き換える、つまり昇順にすると答えが変わります。昇順だと $\kappa[j - w_i]$ がすでに $i$ 回目の更新を受けており、品物 $i$ を 2 回以上使った値が混ざるからです。これは 0-1 ナップサックとしては誤りですが、各品物を何個でも使ってよい問題の正解になります（Exercise 8.3）。1 文字の違いが解く問題を変える、動的計画法らしい落とし穴です。

6.3. 擬多項式時間という落とし穴

Corollary 6.4 は嬉しい結果ですが、注意が要ります。計算量は入力のサイズの関数として測るのが約束でした（計算量と O 記法、Definition 2.3［Complexity and Big-O Notation］）。ナップサック問題の入力を 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}$ ならば真の多項式時間アルゴリズム（Definition 7.1［Complexity and Big-O Notation］）は存在しません（P≠NP予想とは何か）。動的計画法は万能の魔法ではなく、「数値が小さいときに限って指数の壁を回避できる」道具なのだ、と理解してください。

7. 設計の手順と、もう一つの例

ここまでの例から、動的計画法の設計手順を取り出せます。

1. 部分問題を決める。 何を添字にするか。Example 5.2 が示すように、添字は「上位の問題を解くのに必要な情報をすべて含む」必要があります。
2. 漸化式を立てる。 最適解の「最後の一手」で場合分けするのが定石です。ナップサックでは「品物 $i$ を入れたか」でした。
3. 基底を決める。 添字が最小のところで、直接値が定まるようにします。
4. 順序と復元を決める。 依存グラフの位相順序でループを書き、必要なら解を復元する情報を残します。

この手順を、文字列の比較に使う編集距離に当てはめます。

Definition 7.1（編集距離（レーベンシュタイン距離））

有限アルファベット上の文字列 $x$、$y$ に対し、次の 3 種の操作をそれぞれコスト $1$ として、$x$ を $y$ に変換する操作列のうちコストの総和が最小のものの値を編集距離 $d(x,y)$ と呼ぶ。

• 1 文字の削除
• 1 文字の挿入
• 1 文字を別の 1 文字に置換

Remark 7.2（アライメントによる特徴づけ）

証明にはアライメントによる言い換えを使います。$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 章にあります。以下ではこの特徴づけを既知として使います。

Theorem 7.3（編集距離の漸化式）

$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$ を表す。

Proof（Theorem 7.3）

Remark 7.2 により、$D(i,j)$ を $x_1\cdots x_i$ と $y_1 \cdots y_j$ のアライメントの最小コストとして扱います。

基底。 $x_1 \cdots x_i$ と空文字列のアライメントは、$b_t$ がすべてギャップでなければならないので、列は $(x_1, -), \ldots, (x_i, -)$ の $i$ 個に限られます。各列のコストは $1$ なので合計 $i$、これが唯一のアライメントなので $D(i,0) = i$ です。$D(0,j) = j$ も同様です。

$\le$ の向き。 $1 \le i \le m$、$1 \le j \le n$ とします。$x_1\cdots x_{i-1}$ と $y_1 \cdots y_j$ の最小コストのアライメントの右端に、列 $(x_i, -)$ を付け足すと、$x_1 \cdots x_i$ と $y_1 \cdots y_j$ のアライメントが得られ、そのコストは $D(i-1,j) + 1$ です。$D(i,j)$ は最小値ですから $D(i,j) \le D(i-1,j) + 1$。同様に右端に $(-, y_j)$ を付ければ $D(i,j) \le D(i,j-1)+1$、$(x_i, y_j)$ を付ければ $D(i,j) \le D(i-1,j-1) + [x_i \ne y_j]$ が従います。3 つすべてが成り立つので、$D(i,j)$ は右辺の $\min$ 以下です。

$\ge$ の向き。 $x_1 \cdots x_i$ と $y_1\cdots y_j$ の最小コストのアライメント $A$ を 1 つとり、その最後の列 $(a_\ell, b_\ell)$ を見ます。$i, j \ge 1$ より $A$ は空でなく、また両方ギャップの列は許されないので、可能性は次の 3 つだけです。

• $(x_i, -)$ の場合：最後の列を除いた $A'$ は $x_1\cdots x_{i-1}$ と $y_1 \cdots y_j$ のアライメントであり、コストは $\mathrm{cost}(A) - 1$ です。$D(i-1,j)$ は最小値なので $D(i-1,j) \le \mathrm{cost}(A) - 1 = D(i,j) - 1$、すなわち $D(i,j) \ge D(i-1,j) + 1$。
• $(-, y_j)$ の場合：同様に $D(i,j) \ge D(i,j-1) + 1$。
• $(x_i, y_j)$ の場合：最後の列を除いた $A'$ は $x_1 \cdots x_{i-1}$ と $y_1 \cdots y_{j-1}$ のアライメントで、コストは $\mathrm{cost}(A) - [x_i \ne y_j]$ です。よって $D(i,j) \ge D(i-1,j-1) + [x_i \ne y_j]$。

いずれの場合も $D(i,j)$ は右辺の 3 つの量のうち少なくとも 1 つ以上なので、$D(i,j) \ge \min$（3 つの量の最小値）が成り立ちます。両向きを合わせて等号が示されました。

∎

依存グラフの辺は $(i-1,j)$、$(i,j-1)$、$(i-1,j-1)$ から $(i,j)$ へ向かい、辺を辿るたびに $i + j$ が必ず増えるので閉路はありません。部分問題は $(m+1)(n+1)$ 個、遷移は $O(1)$ なので、Theorem 3.2 より計算時間は $O(mn)$、領域は $O(mn)$ です（1 行ずつ捨てれば $O(\min\{m,n\})$ にできます）。

Example 7.4（kitten と sitting の編集距離）

$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. 演習

Exercise 8.1易

Proposition 4.1 を使って、fib_naive(100) の関数呼び出し回数を求め、1 秒間に $10^9$ 回の呼び出しを処理できる計算機での実行時間を年単位で見積もってください。$F_{101} = 573{,}147{,}844{,}013{,}817{,}084{,}101$ を用いてよいものとします。

Solution

Proposition 4.1 より呼び出し回数は

$$T(100) = 2F_{101} - 1 = 1{,}146{,}295{,}688{,}027{,}634{,}168{,}201 \approx 1.15 \times 10^{21}$$

回です。$10^9$ 回毎秒で割ると $1.15 \times 10^{12}$ 秒。1 年は約 $3.156 \times 10^{7}$ 秒なので

$$\frac{1.15 \times 10^{12}}{3.156 \times 10^{7}} \approx 3.6 \times 10^{4}$$

年、およそ 3 万 6 千年です。一方 Corollary 4.2 の方法なら加算 99 回で終わります。同じ再帰式から出発しても、計算の組み立て方でこれだけ差がつきます。

Exercise 8.2標準

硬貨の額面 $c_1, \ldots, c_k \in \mathbb{Z}_{\ge 1}$ が与えられ、各額面は何枚でも使えるとします。金額 $A \in \mathbb{Z}_{\ge 0}$ をちょうど作るのに必要な硬貨の最小枚数 $M(A)$ を求める漸化式を立て、計算量を Theorem 3.2 で評価してください。また、額面が $\{1, 4, 5\}$、$A = 8$ のとき、「大きい額面から貪欲に取る」方法が最適でないことを確かめてください。

Solution

漸化式。 部分問題を「金額 $a$ をちょうど作る最小枚数 $M(a)$」（$0 \le a \le A$）とします。作れないときは $M(a) = +\infty$ と約束します。最後に使った硬貨の額面 $c_t$ で場合分けすると

$$M(0) = 0, \qquad M(a) = \min\bigl\{\, M(a - c_t) + 1 \ :\ 1 \le t \le k,\ c_t \le a \,\bigr\} \quad (a \ge 1)$$

です（$c_t \le a$ を満たす $t$ が 1 つもなければ $M(a) = +\infty$）。正しさは、金額 $a$ を作る最小の硬貨の多重集合から硬貨 1 枚（額面 $c_t$）を取り除くと金額 $a - c_t$ を作る多重集合になり、逆に $a - c_t$ を作る多重集合に $c_t$ を 1 枚足すと $a$ を作る多重集合になる、という対応から従います（Theorem 6.2 と同じ形の議論です）。

計算量。 部分問題は $A+1$ 個、各遷移は最大 $k$ 回の比較なので $c(a) \le c \cdot k$。$c_t \ge 1$ より $a - c_t < a$ なので依存グラフは DAG です。Theorem 3.2 より $O(kA)$ 時間、$O(A)$ 領域です。

貪欲法の反例。 $\{1,4,5\}$、$A = 8$ で貪欲に取ると、$5 \to$ 残り $3 \to 1,1,1$ で 4 枚です。しかし漸化式で表を埋めると

$a$	0	1	2	3	4	5	6	7	8
$M(a)$	0	1	2	3	1	1	2	3	2

となり、$M(8) = 2$ です。実際 $8 = 4 + 4$ で 2 枚です。$M(8) = \min\{M(7)+1,\ M(4)+1,\ M(3)+1\} = \min\{4, 2, 4\} = 2$ と計算されています。貪欲法は「最初の 1 手を確定させる」ため、後の選択肢を壊すことがあります。動的計画法は全ての選択肢を残したまま比較する点が違います。

Exercise 8.3標準

Definition 6.1 と同じ入力に対し、各品物を何個でも使ってよいとした問題（無限ナップサック問題）を考えます。$K'(i,j)$ を「品物 $1, \ldots, i$ を何個でも使えて容量 $j$ のときの最大価値」として漸化式を立て、証明してください。また Proposition 6.6 の 1 次元アルゴリズムで $j$ を昇順に回すとこの問題の答えが得られる理由を説明してください。

Solution

漸化式。 $1 \le i \le n$、$w_i \le j \le W$ のとき

$$K'(i,j) = \max\bigl\{\, K'(i-1, j),\ \ v_i + K'(i,\ j - w_i) \,\bigr\}$$

であり、$j < w_i$ のときは $K'(i,j) = K'(i-1,j)$、$K'(0,j) = 0$ です。第 2 項の第 1 添字が $i-1$ ではなく $i$ である点が Theorem 6.2 との違いです。

証明は同じ形です。品物 $i$ の使用個数が $0$ 個である多重集合の全体を $\mathcal{A}$、$1$ 個以上である全体を $\mathcal{B}$ とすると、$\mathcal{A}$ 側の最大値は $K'(i-1,j)$ です。$\mathcal{B}$ 側については、品物 $i$ を 1 個取り除く写像が $\mathcal{B}$ から「品物 $1,\ldots,i$ を使い容量 $j - w_i$ 以下の多重集合の全体」への全単射になり（逆写像は品物 $i$ を 1 個足す操作）、価値は $v_i$ だけ減るので、最大値は $v_i + K'(i, j-w_i)$ です。取り除いた後も品物 $i$ を使ってよいので添字が $i$ のまま残る、というのが違いのすべてです。依存グラフは、辺を辿るたびに $(i,j)$ の $i + j$ が真に増えるので DAG です。

昇順でよい理由。 1 次元配列 $\kappa$ で $j$ を昇順に回すと、$\kappa[j]$ を更新する時点で $\kappa[j - w_i]$ は $j - w_i < j$ よりすでに $i$ 回目の更新を受け終わっています。Proposition 6.6 と同じ帰納法をたどれば、その値は $K'(i, j-w_i)$ です。また $\kappa[j]$ 自身はまだ $i$ 回目の更新前なので $K'(i-1,j)$ です。よって代入結果は $\max\{K'(i-1,j),\ v_i + K'(i, j-w_i)\} = K'(i,j)$ となり、上の漸化式そのものになります。降順が 0-1 版、昇順が無限版、という対応です。

Exercise 8.4難

実数列 $a_1, a_2, \ldots, a_n$ に対し、添字が増加し値も狭義単調増加する部分列の最大長を求める問題（最長増加部分列）を考えます。$L(i)$ を「$a_i$ で終わる増加部分列の最大長」として漸化式を立て、$O(n^2)$ で解けることを示してください。さらに $a = (3,1,4,1,5,9,2,6)$ で計算してください。

Solution

漸化式。 $L(i) = 1 + \max\bigl(\{L(j) : 1 \le j < i,\ a_j < a_i\} \cup \{0\}\bigr)$ とします。空集合との合併は「条件を満たす $j$ がないときは $\max$ を $0$ とする」ための約束で、そのとき $L(i) = 1$ です。

正しさを見ます。$a_i$ で終わる最長の増加部分列を $a_{j_1} < a_{j_2} < \cdots < a_{j_r} = a_i$（$j_r = i$）とします。$r = 1$ なら $L(i) = 1$ で式は正しい。$r \ge 2$ なら、末尾を除いた $a_{j_1}, \ldots, a_{j_{r-1}}$ は $a_{j_{r-1}}$ で終わる増加部分列であり、$j_{r-1} < i$ かつ $a_{j_{r-1}} < a_i$ なので $r - 1 \le L(j_{r-1})$、よって $L(i) \le 1 + \max\{L(j) : \cdots\}$。逆に、条件を満たす任意の $j$ について、$a_j$ で終わる最長増加部分列の後ろに $a_i$ を付ければ長さ $L(j) + 1$ の増加部分列（$a_j < a_i$ なので単調性は保たれます）が作れるので $L(i) \ge L(j) + 1$。両向きで等号です。

答えは $\max_{1 \le i \le n} L(i)$ です。部分問題は $n$ 個、$L(i)$ の計算に $j = 1, \ldots, i-1$ の走査で $O(n)$ かかるので、Theorem 3.2 より $\sum_i c(i) = O(n^2)$ です。依存グラフは添字が真に増える向きの辺だけなので DAG です。

計算。 $a = (3,1,4,1,5,9,2,6)$ で左から求めます。$L(1) = 1$（$a_1=3$、左に何もない）。$L(2) = 1$（$a_2 = 1$ より小さい値が左にない）。$L(3)$：$a_3 = 4$ より小さいのは $a_1 = 3, a_2 = 1$ で $\max\{1,1\} = 1$、よって $2$。$L(4) = 1$（$a_4 = 1$）。$L(5)$：$a_5 = 5$ より小さいのは $a_1,a_2,a_3,a_4$ で $\max\{1,1,2,1\} = 2$、よって $3$。$L(6)$：$a_6 = 9$ より小さいのは全部で $\max\{1,1,2,1,3\} = 3$、よって $4$。$L(7)$：$a_7 = 2$ より小さいのは $a_2 = 1, a_4 = 1$ で $\max\{1,1\}=1$、よって $2$。$L(8)$：$a_8 = 6$ より小さいのは $a_1,a_2,a_3,a_4,a_5,a_7$ で $\max\{1,1,2,1,3,2\} = 3$、よって $4$。

$(L(i)) = (1,1,2,1,3,4,2,4)$ で、答えは $4$ です。$L(6) = 4$ を達成するのは $1, 4, 5, 9$（$a_2, a_3, a_5, a_6$）などです。

なお、「長さごとの末尾の最小値」を配列で管理すると、各 $i$ での探索を二分探索に置き換えて $O(n \log n)$ にできます（探索アルゴリズム、Theorem 3.3［探索アルゴリズム］）。動的計画法の計算量は、遷移の計算をデータ構造で加速することでさらに下げられることがあります。

参考文献

• 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: 同じ問題に対する別の動的計画法

価値を添字にする。 Definition 6.1 のナップサック問題で、価値 $v_i$ がすべて非負整数だとします。Corollary 6.4 の $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$）です。Theorem 6.2 とまったく同じ全単射の議論により、$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)$ 個なので、Theorem 3.2 より $O(nV)$ 時間です。

Example 6.5 の例では $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 困難性が「厳密解の多項式時間計算」を阻んでも、近似ならこの壁を越えられることがあります。