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

考え方（動的計画法）
$n$ 円を最小枚数で払うとき、最後に使う硬貨を $c$ 円（$c=1,4,6$ のいずれか）とすると、残りの $n-c$ 円も最小枚数で払うのが最善である。そのため $M(n)={\min }_c\{M(n-c)+1\}$ が成り立つ。小さい $n$ から順に表を埋めていけば、必要な値はいつもすでに計算済みになっている。

表を埋める
$M(0)=0$ から始める。
- $M(1)=M(0)+1=1$
- $M(2)=M(1)+1=2$
- $M(3)=M(2)+1=3$
- $M(4)=\min \{M(3)+1,M(0)+1\}=\min \{4,1\}=1$
- $M(5)=\min \{M(4)+1,M(1)+1\}=\min \{2,2\}=2$
- $M(6)=\min \{M(5)+1,M(2)+1,M(0)+1\}=\min \{3,3,1\}=1$
- $M(7)=\min \{M(6)+1,M(3)+1,M(1)+1\}=\min \{2,4,2\}=2$
- $M(8)=\min \{M(7)+1,M(4)+1,M(2)+1\}=\min \{3,2,3\}=2$
- $M(9)=\min \{M(8)+1,M(5)+1,M(3)+1\}=\min \{3,3,4\}=3$
- $M(10)=\min \{M(9)+1,M(6)+1,M(4)+1\}=\min \{4,2,2\}=2$
- $M(11)=\min \{M(10)+1,M(7)+1,M(5)+1\}=\min \{3,3,3\}=3$
- $M(12)=\min \{M(11)+1,M(8)+1,M(6)+1\}=\min \{4,3,2\}=2$
- $M(13)=\min \{M(12)+1,M(9)+1,M(7)+1\}=\min \{3,4,3\}=3$
- $M(14)=\min \{M(13)+1,M(10)+1,M(8)+1\}=\min \{4,3,3\}=3$

よって $M(14)=3$ である（例えば $14=6+4+4$）。

参考：大きい硬貨から順に使う方法（貪欲法）では $14=6+6+1+1$ の $4$ 枚になり、最小にならない。表を埋める方法なら、このような場合でも正しく最小値が求まる。

漸化式で表を順に埋める。
$M(0)=0$
$M(1)=M(0)+1=1$
$M(2)=M(1)+1=2$
$M(3)=M(2)+1=3$
$M(4)=\min \{M(3)+1,M(0)+1\}=1$
$M(5)=\min \{M(4)+1,M(1)+1\}=2$
$M(6)=\min \{M(5)+1,M(2)+1,M(0)+1\}=1$
$M(7)=\min \{M(6)+1,M(3)+1,M(1)+1\}=2$
$M(8)=\min \{M(7)+1,M(4)+1,M(2)+1\}=\min \{3,2,3\}=2$
$M(9)=\min \{M(8)+1,M(5)+1,M(3)+1\}=\min \{3,3,4\}=3$
$M(10)=\min \{M(9)+1,M(6)+1,M(4)+1\}=\min \{4,2,2\}=2$
$M(11)=\min \{M(10)+1,M(7)+1,M(5)+1\}=\min \{3,3,3\}=3$
$M(12)=\min \{M(11)+1,M(8)+1,M(6)+1\}=\min \{4,3,2\}=2$
$M(13)=\min \{M(12)+1,M(9)+1,M(7)+1\}=\min \{3,4,3\}=3$
$M(14)=\min \{M(13)+1,M(10)+1,M(8)+1\}=\min \{4,3,3\}=3$

検算：$14=6+4+4$ で 3 枚。2 枚で作れる金額は $2,5,7,8,10,12$ などで、$14$ は含まれない（$6+6=12$、$6+4=10$、$4+4=8$ など）。1 枚でも不可能。よって最小は 3 枚。