2441: 零钱兑换

内存限制:256 MB 时间限制:5 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:6 通过:5

题目描述

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

输入格式

第一行输入一个n,表示不同面额的硬币的硬币种类(n<=40)
第二行输入n个不同的面值a[i]<231-1
第三行输入一个整数表示总金额 amount<=104

输出格式

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

输入样例 复制

3
1 2 5
11

输出样例 复制

3

分类标签