質問: min(dp[r], dp[r - k*money[c]] + k); } } } printf("%d\n", dp[M]); } int main(void) { solve(); print(); return(0); } ``` 普通に考えれば、20G支払うのに12Gを1枚、5Gを1枚、1Gを3枚で計5枚が最小枚数となるはずです。 ですが、答えは4と出力されてしまいます。 どうやら、15円支払う際の最小枚数及び20円支払う際の最小枚数が間違っているようなのです。 原因について考えてみたのですが、わかりません。 どなたか教えていただけないでしょうか? また、動的計画法について、プログラミングコンテストチャレンジブックという本のアルゴリズムを写経しながら勉強している途中なので、理解が薄い状況です。誠に身勝手ですが、その点も踏まえて回答していただけると嬉しいです。
回答: 15は5Gが3枚、20は5Gが4枚がそれぞれ最小で合ってると思います。