【贪心4】零钱兑换问题

题目简述：

给定一组硬币的面额，其中包含面额 1 且相邻面额满足倍数关系，和一个目标金额 amount。要求找出最少的硬币数目，使得硬币的总金额等于目标金额。如果无法组合成目标金额，返回 -1。

题目描述：

给定一组不同面额的硬币（保证包含面额 1 在起始位置，且相邻面额是倍数关系），和一个目标金额 amount，要求你找出最少的硬币数目，使得硬币的总金额等于目标金额。

要求：

• 你可以使用任意数量的硬币。
• 你需要选择硬币的组合，使得总金额等于目标金额，并且硬币的数量最少。
• 如果无法组合成目标金额，返回 -1。

输入格式：

• 第一行包含一个整数 n，表示硬币的数量。$1$ ≤ n ≤ $20$
• 第二行包含 n 个整数，表示硬币的面额coins，保证每个面额都大于0且相邻的面额满足倍数关系，且包含面额 1。$1$ ≤ coins[i] ≤ $10^9$, coins[0] = $1$
• 第三行包含一个整数 amount，表示目标金额。$1$ ≤ amount ≤ $10^9$

输出格式：

• 输出一个整数，表示能够凑成目标金额所需的最少硬币数目。如果无法凑成目标金额，输出 -1。

示例：

输入：

5
1 5 10 20 100
66

输出：

5

说明：

• 你可以选择硬币 20 + 20 + 20 + 5 + 1，总金额为 11，硬币数目为 3。
• 所以最少硬币数为 5。