【贪心4】零钱兑换问题
题目简述：
给定一组硬币的面额，其中包含面额 1 且相邻面额满足倍数关系，和一个目标金额 amount。要求找出最少的硬币数目，使得硬币的总金额等于目标金额。如果无法组合成目标金额，返回 -1。
P14068.【贪心4】零钱兑换问题
题目描述：
给定一组不同面额的硬币（保证包含面额 1 在起始位置，且相邻面额是倍数关系），和一个目标金额 amount，要求你找出最少的硬币数目，使得硬币的总金额等于目标金额。
要求：
- 你可以使用任意数量的硬币。
- 你需要选择硬币的组合，使得总金额等于目标金额，并且硬币的数量最少。
- 如果无法组合成目标金额，返回
-1。
输入格式：
- 第一行包含一个整数
n，表示硬币的数量。1 ≤ n ≤ 20
- 第二行包含
n 个整数，表示硬币的面额coins，保证每个面额都大于0且相邻的面额满足倍数关系，且包含面额 1。1 ≤ coins[i] ≤ 109, coins[0] = 1
- 第三行包含一个整数
amount，表示目标金额。1 ≤ amount ≤ 109
输出格式：
- 输出一个整数，表示能够凑成目标金额所需的最少硬币数目。如果无法凑成目标金额，输出
-1。
示例：
输入：
5
1 5 10 20 100
66
输出：
5
说明：
- 你可以选择硬币
20 + 20 + 20 + 5 + 1，总金额为 11，硬币数目为 3。
- 所以最少硬币数为
5。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
