首页 > 试题广场 >

换钱的方法数

[编程题]换钱的方法数

热度指数：7363 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组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

备注:

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

算法知识视频讲解

快支棱起来的椰子很愤怒

发表于 2022-01-10 18:56:07

n, aim = map(int, input().split()) nums = list(map(int, input().split())) dp = [0] * (aim + 1) dp[0] = 1 for i in range(n): for j in range(nums[i] 展开全文

Bruce_Lee_

发表于 2021-03-05 18:45:14

话不多说上代码。解释书上有。import java.util.Scanner; public class Main{public static final int mod = 1_000_000_007; public static int coins1(int[] arr, int aim){ 展开全文