アルゴリズムと計算量の問題

動的計画法では、小さい金額から順に $f(n)$ の値を表に書き込んでいく。$n$ 円を払うとき、最後に使う硬貨を $c$ 円（$c=1,4,5$、ただし $c\le n$）とすると、残りの $n-c$ 円は最小 $f(n-c)$ 枚で払えるので、全体の枚数は $f(n-c)+1$ 枚になる。そのうち最小のものが $f(n)$ である。

$f(0)=0$ から始めて計算する。
- $f(1)=f(0)+1=1$
- $f(2)=f(1)+1=2$
- $f(3)=f(2)+1=3$
- $f(4)=\min \{f(3)+1,f(0)+1\}=\min \{4,1\}=1$
- $f(5)=\min \{f(4)+1,f(1)+1,f(0)+1\}=\min \{2,2,1\}=1$
- $f(6)=\min \{f(5)+1,f(2)+1,f(1)+1\}=\min \{2,3,2\}=2$
- $f(7)=\min \{f(6)+1,f(3)+1,f(2)+1\}=\min \{3,4,3\}=3$
- $f(8)=\min \{f(7)+1,f(4)+1,f(3)+1\}=\min \{4,2,4\}=2$
- $f(9)=\min \{f(8)+1,f(5)+1,f(4)+1\}=\min \{3,2,2\}=2$
- $f(10)=\min \{f(9)+1,f(6)+1,f(5)+1\}=\min \{3,3,2\}=2$
- $f(11)=\min \{f(10)+1,f(7)+1,f(6)+1\}=\min \{3,4,3\}=3$
- $f(12)=\min \{f(11)+1,f(8)+1,f(7)+1\}=\min \{4,3,4\}=3$

表にまとめると次のとおり。
$$\begin{array}{cccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ f(n)& 0& 1& 2& 3& 1& 1& 2& 3& 2& 2& 2& 3& 3\end{array}$$

よって $f(12)=3$ である（実際、$4+4+4=12$ で $3$ 枚）。なお、大きい硬貨から使う方法では $5+5+1+1$ の $4$ 枚となり、最小にならない。

漸化式で順に計算する。
$f(0)=0$
$f(1)=f(0)+1=1$
$f(2)=f(1)+1=2$
$f(3)=f(2)+1=3$
$f(4)=\min \{f(3)+1,f(0)+1\}=\min \{4,1\}=1$
$f(5)=\min \{f(4)+1,f(1)+1,f(0)+1\}=\min \{2,2,1\}=1$
$f(6)=\min \{f(5)+1,f(2)+1,f(1)+1\}=\min \{2,3,2\}=2$
$f(7)=\min \{f(6)+1,f(3)+1,f(2)+1\}=\min \{3,4,3\}=3$
$f(8)=\min \{f(7)+1,f(4)+1,f(3)+1\}=\min \{4,2,4\}=2$
$f(9)=\min \{f(8)+1,f(5)+1,f(4)+1\}=\min \{3,2,2\}=2$
$f(10)=\min \{f(9)+1,f(6)+1,f(5)+1\}=\min \{3,3,2\}=2$
$f(11)=\min \{f(10)+1,f(7)+1,f(6)+1\}=\min \{3,4,3\}=3$
$f(12)=\min \{f(11)+1,f(8)+1,f(7)+1\}=\min \{4,3,4\}=3$

検算：12 = 4+4+4 の 3 枚で支払える。2 枚では、可能な和は 2,5,6,8,9,10 のみで 12 にならないので、最小は 3 枚。よって $f(12)=3$。