AlgoMooc
← 返回题库

P5920. 零钱兑换

困难通过率 83% · 提交 6 · 通过 5
动态规划背包DP哈希表DP

小慕正在整理他的收藏架,架子上有若干种不同面值的纪念币,每种面值的纪念币数量不限。现在他需要凑出恰好等于目标金额 的零钱,请问最少需要多少张纪念币? 如果无法凑出目标金额,请返回 -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

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。