動的計画法の基本（硬貨の最小枚数）

$O (n) = min_{c} {O (n - c) + 1}$ のような 1 次元の漸化式で表を埋め、 $n$ 円を払う硬貨の最小枚数を求められる

前提

中学までに習ったことだけで始められます。

説明

硬貨の種類がいくつか与えられたとき、ちょうど $n$ 円を払うのに必要な硬貨の最小枚数を求める方法を学びます。小さい金額の答えを表にして、それを使って大きい金額の答えを順に決めていくのが「動的計画法」の考え方です。各金額の答えは1つの式（漸化式）で求められるので、計算は表を左から右へ埋めていくだけで済みます。大きい硬貨から貪欲に使う方法では最小にならない硬貨の組でも、この方法なら正しい答えが出ます。

なぜそうしてよいのか

硬貨の金額の集合を $C$ （例えば ${1, 3, 4}$ ）とし、ちょうど $m$ 円を払う最小枚数を $O (m)$ と書きます。 $0$ 円は硬貨を1枚も使わずに払えるので $O (0) = 0$ です。 $m \geq 1$ のとき、 $m$ 円の払い方を1つ考え、その中の硬貨を1枚選んで「最後の1枚」と呼びます。その金額を $c$ とすると、残りの硬貨でちょうど $m - c$ 円を払っていることになります。残りの枚数は少なくとも $O (m - c)$ 枚なので、全体は少なくとも $O (m - c) + 1$ 枚です。逆に、 $m - c$ 円を $O (m - c)$ 枚で払う方法に硬貨 $c$ を1枚足せば、 $m$ 円を $O (m - c) + 1$ 枚で払えます。

最後の1枚として考えられるのは、 $c \leq m$ をみたす硬貨 $c \in C$ だけです。よって、その全部の候補の中で最も少ないものが答えになります。
$O (m) = c \in C, c \leq m min {O (m - c) + 1}$
右辺には $m$ より小さい金額の値しか出てきません。そのため $O (0), O (1), O (2), \dots$ の順に表を埋めれば、どの値も必要なときにはすでに求まっています。ちょうど払えない金額 $m$ には $O (m) = \infty$ （払えない印）を入れ、 $\infty + 1 = \infty$ として扱います。

手順

硬貨の集合 $C$ と目標金額 $n$ を確認し、 $0$ から $n$ までの表を用意する
初期値を $O (0) = 0$ と書き込む
$m = 1, 2, \dots, n$ の順に、 $c \leq m$ をみたす各硬貨 $c \in C$ について候補 $O (m - c) + 1$ を計算する（払えない金額は $\infty$ とする）
候補の最小値を $O (m)$ として表に書き込む： $O (m) = min_{c \in C, c \leq m} {O (m - c) + 1}$ 。候補が1つもないか、すべて $\infty$ なら $O (m) = \infty$ とする
表の $O (n)$ を読み取る。これが求める最小枚数である（ $\infty$ ならちょうど払えない）

例題

1円、3円、4円の3種類の硬貨が何枚でも使えるとする。ちょうど6円を払うのに必要な硬貨の最小枚数を求めよ。

例題の解答

手順1： $C = {1, 3, 4}$ 、 $n = 6$ とし、 $O (0)$ から $O (6)$ までの表を用意する。
手順2： $O (0) = 0$ とする。
手順3・4： $m = 1$ から順に候補を計算し、その最小値を書き込む。
- $O (1)$ ： $c = 1$ だけが使えるので、 $O (0) + 1 = 1$ 。よって $O (1) = 1$ 。
- $O (2)$ ： $c = 1$ だけが使えるので、 $O (1) + 1 = 2$ 。よって $O (2) = 2$ 。
- $O (3)$ ：候補は $c = 1$ のとき $O (2) + 1 = 3$ 、 $c = 3$ のとき $O (0) + 1 = 1$ 。よって $O (3) = 1$ 。
- $O (4)$ ：候補は $c = 1$ のとき $O (3) + 1 = 2$ 、 $c = 3$ のとき $O (1) + 1 = 2$ 、 $c = 4$ のとき $O (0) + 1 = 1$ 。よって $O (4) = 1$ 。
- $O (5)$ ：候補は $c = 1$ のとき $O (4) + 1 = 2$ 、 $c = 3$ のとき $O (2) + 1 = 3$ 、 $c = 4$ のとき $O (1) + 1 = 2$ 。よって $O (5) = 2$ 。
- $O (6)$ ：候補は $c = 1$ のとき $O (5) + 1 = 3$ 、 $c = 3$ のとき $O (3) + 1 = 2$ 、 $c = 4$ のとき $O (2) + 1 = 3$ 。よって $O (6) = 2$ 。
手順5： $O (6) = 2$ である。実際に $3 + 3 = 6$ の2枚で払える。なお、大きい硬貨から使うと $4 + 1 + 1$ の3枚になり、最小にならない。

答え: $2$

よくある誤り

大きい硬貨から順に使えば最小になると思い込む誤り。硬貨が ${1, 3, 4}$ で6円のとき、この方法では $4 + 1 + 1$ の3枚になる。正しくは表を埋めて $O (6) = 2$ （ $3 + 3$ ）となる。
初期値を $O (0) = 1$ としたり、そもそも書かなかったりする誤り。正しくは、0円は硬貨0枚で払えるので $O (0) = 0$ 。これを誤ると、例えば $O (3) = O (0) + 1$ がずれて表全体が狂う。
$c > m$ の硬貨まで候補に入れて $O (m - c)$ （金額が負になる）を使ってしまう誤り。正しくは $c \leq m$ の硬貨だけを候補にする。例えば $O (2)$ では $c = 3, 4$ は使えず、 $O (2) = O (1) + 1 = 2$ 。
1円硬貨がないときに、ちょうど払えない金額の値を0や空欄のまま計算してしまう誤り。正しくは $O (m) = \infty$ とおく。例えば $C = {2, 5}$ なら $O (1) = \infty$ であり、 $O (6) = min {O (4) + 1, O (1) + 1} = min {3, \infty} = 3$ となる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 4（大学院入試の標準レベル）
$1$ 円、 $7$ 円、 $10$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、 $n$ 円をちょうど支払う硬貨の組み合わせのうち枚数が最小のものの枚数を $O (n)$ とする。また、次の貪欲法で $n$ 円を支払ったときの枚数を $G (n)$ とする。
貪欲法：残りの金額が $0$ になるまで、残りの金額以下で額面が最大の硬貨を $1$ 枚使う。
$1 ≦ n ≦ 100$ を満たす整数 $n$ のうち、 $G (n) > O (n)$ となるものの個数を求めよ。

この技能の次に学べること

貪欲法が最適でない場合の判定（大学数学アルゴリズムと計算量）
0-1 ナップサック問題の動的計画法（大学数学アルゴリズムと計算量）
編集距離（大学数学アルゴリズムと計算量）
最長共通部分列（大学数学アルゴリズムと計算量）