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

考え方：$n$ 円を最小枚数で払う払い方で、最後に使う $1$ 枚の硬貨を $c$ 円とすると、残りの $n-c$ 円も最小枚数で払われているはずです。したがって $M(n)$ は、$c=1,3,4$（ただし $c\le n$）について $M(n-c)+1$ を比べた最小値になります。$M(0)=0$ から始めて、$n=1,2,\dots ,10$ の順に表を埋めます。

• $M(1)=M(0)+1=1$
• $M(2)=M(1)+1=2$
• $M(3)=\min \{M(2)+1,M(0)+1\}=\min \{3,1\}=1$
• $M(4)=\min \{M(3)+1,M(1)+1,M(0)+1\}=\min \{2,2,1\}=1$
• $M(5)=\min \{M(4)+1,M(2)+1,M(1)+1\}=\min \{2,3,2\}=2$
• $M(6)=\min \{M(5)+1,M(3)+1,M(2)+1\}=\min \{3,2,3\}=2$
• $M(7)=\min \{M(6)+1,M(4)+1,M(3)+1\}=\min \{3,2,2\}=2$
• $M(8)=\min \{M(7)+1,M(5)+1,M(4)+1\}=\min \{3,3,2\}=2$
• $M(9)=\min \{M(8)+1,M(6)+1,M(5)+1\}=\min \{3,3,3\}=3$
• $M(10)=\min \{M(9)+1,M(7)+1,M(6)+1\}=\min \{4,3,3\}=3$

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

よって $M(10)=3$ です。実際、$10=3+3+4$ と $3$ 枚で払えます（$2$ 枚では最大でも $8$ 円なので払えません）。なお、大きい硬貨から順に使う方法（貪欲法）では $4+4+1+1$ の $4$ 枚になり、最小になりません。

答え：$3$

漸化式を $n=1$ から順に計算する。
$M(0)=0$。
$M(1)=M(0)+1=1$。
$M(2)=M(1)+1=2$。
$M(3)=\min \{M(2)+1,M(0)+1\}=\min \{3,1\}=1$。
$M(4)=\min \{M(3)+1,M(1)+1,M(0)+1\}=\min \{2,2,1\}=1$。
$M(5)=\min \{M(4)+1,M(2)+1,M(1)+1\}=\min \{2,3,2\}=2$。
$M(6)=\min \{M(5)+1,M(3)+1,M(2)+1\}=\min \{3,2,3\}=2$。
$M(7)=\min \{M(6)+1,M(4)+1,M(3)+1\}=\min \{3,2,2\}=2$。
$M(8)=\min \{M(7)+1,M(5)+1,M(4)+1\}=\min \{3,3,2\}=2$。
$M(9)=\min \{M(8)+1,M(6)+1,M(5)+1\}=\min \{3,3,3\}=3$。
$M(10)=\min \{M(9)+1,M(7)+1,M(6)+1\}=\min \{4,3,3\}=3$。

検算：$10=4+3+3$ の 3 枚で支払える。2 枚では最大でも $4+4=8<10$ なので不可能。よって最小は 3 枚で、$M(10)=3$。