首页 > 试题广场 >

换钱的方法数

[编程题]换钱的方法数

给定数组arr，设数组长度为n，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求换钱的方法数有多少种。由于方法的种数比较大，所以要求输出对 $10^9+7$ 进行取模后的答案。

输出包括两行，第一行包括两个整数n和aim。第二行包含n个整数，表示arr数组。

输出一个整数，表示换钱的方法数对取模后的答案。

示例1

输入

4 15
5 10 25 1

5*3=15

10*1+5*1=15

10*1+1*5=15

1*10+5*1=15

5*2+1*5=15

1*15=15

示例2

5 1000
2 3 5 7 10

20932712

时间复杂度,空间复杂度。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划

上传者：小小

难度：

0条回答 43收藏 5072浏览

查看代码

换钱的方法数

扫一扫，把题目装进口袋