小慕正在整理他的收藏架,架子上有若干种不同面值的纪念币,每种面值的纪念币数量不限。现在他需要凑出恰好等于目标金额 的零钱,请问最少需要多少张纪念币? 如果无法凑出目标金额,请返回 -1。
提示:带虚线的词点一下有通俗解释。
输入描述
第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。 第二行给定 n 个正整数表示 arr 数组中的所有元素 其中,0 <= n <= 10000,0 < arr[i] <= 10000,0 <= aim <= 5000
输出描述
输出组成 aim 的最少货币数
示例
示例 1
输入
3 20 5 2 3
输出
4
时间限制 1000 ms · 内存限制 128 MB