硬貨が 1 円、3 円、4 円の 3 種類あり、各硬貨は何枚でも使えるとき、ちょうど 6 円を作るのに必要な最小の枚数はいくつですか？

3 円玉 2 枚で 3 + 3 = 6 円になるため、最小枚数は 2 枚です。大きい硬貨から順に使う貪欲法では、4 円玉を 1 枚使い、残り 2 円を 1 円玉 2 枚で払うので合計 3 枚になり、最適解になりません。この硬貨の組み合わせでは貪欲法が最適解を保証できないため、動的計画法で 1 円から順に最小枚数を求める必要があります。dp[6] = min(dp[5], dp[3], dp[2]) + 1 = 2 と計算できます。