首页 > 试题广场 >

凑硬币

[编程题]凑硬币
  • 热度指数：220 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

输入描述:
第一行两个个整数N和K， N代表需要达到的总金额，K代表有K种面额的硬币，用空格分隔。

第二行为K个整数a1,a2...ak，用空格分隔，代表K种面额的硬币。


输出描述:
一个整数代表用所给面额的硬币组合成N的方案数。
示例1

输入

5 3
1 2 5

输出

4

说明

5 = 5

5 = 2 + 2 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

备注:
0<=N<=5000,1<=K<=500

1<=ai<=5000,

因为结果很大，请将其对1e9+7(1000000007)取模
算法知识视频讲解
开通博客

暂无题解

问题信息

第四范式 2020 Java工程师
上传者：小小
难度：
1条回答 2129浏览

热门推荐

通过挑战的用户

相关试题

凑硬币

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号