首页 > 试题广场 >

换钱的最少货币数

[编程题]换钱的最少货币数
  • 热度指数:8764 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。

输入描述:
输入包括两行,第一行两个整数n(0<=n<=1000)代表数组长度和aim(0<=aim<=5000),第二行n个不重复的正整数,代表arr


输出描述:
输出一个整数,表示组成aim的最小货币数,无解时输出-1.
示例1

输入

3 20
5 2 3

输出

4

说明

20=5*4
示例2

输入

3 0
5 2 3

输出

0
示例3

输入

2 2
3 5

输出

-1

备注:
时间复杂度,空间复杂度

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