硬币问题

​ 被腾讯的在线笔试题折腾的不轻,这里写一下第一题:动态规划之硬币问题。

​ 题目是这样的:给出n种面值的硬币,和一个数值m,每种面值的硬币数量不限,要求从数值1到m(包括1和m),都能用n种面值的硬币凑出来,求出最少的硬币数。输入的第一行为m和n,接下来的n行为n种面值的硬币。示例如下:

输入:

18 4

1 2 5 10 (这里为了方便我就不换行了)

输出:

5

解释:要保证1-18都能凑出来,发现必须要有两枚面值为2的硬币,比如14,就需要一枚面值为10的硬币和两枚面值为2的硬币,其他的各要一枚就行了,所以是5个硬币。


​ 小插曲:我本以为符合了就开始动博客,结果并不能通过所有测试。。。先挖个坑鸽在这。