 题目

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

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

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

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：
1 <= coins.length <= 12
1 <= coins[i] <= $2^{3}1$- 1
0 <= amount <= $10^4$

 解1

这个问题可以使用动态规划来解决，具体步骤如下：

1. 创建一个长度为 amount + 1 的数组 dp，其中 dp[i] 表示凑成金额 i 需要的最少硬币数，初始值为 amount + 1。

2. 设置 dp[0] = 0，因为凑成金额 0 不需要硬币。

3. 遍历 dp 数组，对于每个金额 i，遍历硬币面额数组 coins，如果当前硬币面额 coin 小于或等于 i，则更新 dp[i] 为 dp[i - coin] + 1，表示使用当前硬币需要的硬币数。选择最小的硬币数。

4. 最终，如果 dp[amount] 仍然为 amount + 1，说明无法凑成总金额，返回 -1，否则返回 dp[amount]。

 java 代码

以下是对应的Java代码实现：

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (coin <= i) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

这个算法的时间复杂度为 O(amount * coinTypes)，其中 amount 是目标金额，coinTypes 是硬币面额种类的数量。

 解2
这段代码实现了一个使用记忆化搜索（Memoization）的动态规划方法来解决硬币找零问题。该问题的目标是找出凑成给定金额所需的最少硬币数量。

1. coinChange 函数接受两个参数：硬币面额数组 coins 和目标金额 amount。首先，检查如果 amount 小于 1，就返回 0。因为无需硬币即可达到目标金额 0。

2. 在 coinChange 函数内部，它调用另一个私有函数 coinChange，该函数额外接受一个数组 count 用于记忆化搜索。这个数组用于存储已经计算过的中间结果。

3. 在 coinChange 函数内部，首先检查如果 rem（余额）小于 0，则返回 -1，表示无法凑成目标金额。如果 rem 等于 0，则返回 0，表示已经凑成目标金额。

4. 进一步，如果 count[rem - 1] 不等于 0，表示已经计算过 rem 这个余额的最小硬币数量，直接返回 count[rem - 1]。

5. 如果以上条件都不满足，就进入实际的动态规划部分。定义一个 min 变量用于存储最小硬币数量，初始值设为整数最大值。

6. 遍历硬币数组 coins 中的每个硬币面额，对于每个硬币，递归调用 coinChange 函数，计算减去当前硬币面额后的余额 rem - coin 的最小硬币数量，并加上 1（因为使用了一个硬币）。将这个结果与 min 比较，更新 min 为较小的值。

7. 最后，将 min 存入 count[rem - 1] 中，表示已经计算了余额为 rem 的最小硬币数量。

8. 返回 count[rem - 1] 作为结果。如果 count[rem - 1] 仍然等于整数最大值，表示无法凑成目标金额，返回 -1。

这段代码使用记忆化搜索减小了重复计算，提高了算法的效率，从而在较大的输入情况下可以更快地找到最小硬币数量。

 java代码2

public class Solution {public int coinChange(int[] coins, int amount) {// 如果目标金额小于 1，直接返回 0if (amount < 1) {return 0;}// 创建一个用于记忆化搜索的数组，存储已经计算过的中间结果return coinChange(coins, amount, new int[amount]);}private int coinChange(int[] coins, int rem, int[] count) {// 如果余额小于 0，无法凑成目标金额，返回 -1if (rem < 0) {return -1;}// 如果余额为 0，表示已经凑成目标金额，返回 0if (rem == 0) {return 0;}// 如果已经计算过余额 rem 的最小硬币数量，直接返回结果if (count[rem - 1] != 0) {return count[rem - 1];}// 初始化最小硬币数量为整数最大值int min = Integer.MAX_VALUE;// 遍历硬币数组，计算每个硬币面额对应的最小硬币数量for (int coin : coins) {// 递归调用 coinChange 函数，计算余额减去当前硬币面额的最小硬币数量int res = coinChange(coins, rem - coin, count);// 如果 res 大于等于 0 并且小于 min，更新 min 为 res + 1if (res >= 0 && res < min) {min = 1 + res;}}// 将计算得到的最小硬币数量存入 count 数组中，以便重复利用count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;// 返回最小硬币数量return count[rem - 1];}
}

 python代码
以下是Python的代码实现，使用动态规划来找到可以凑成总金额所需的最少硬币数量：

class Solution:def coinChange(self, coins, amount):dp = [float('inf')] * (amount + 1)dp[0] = 0for coin in coins:for i in range(coin, amount + 1):dp[i] = min(dp[i], dp[i - coin] + 1)return dp[amount] if dp[amount] != float('inf') else -1

使用动态规划来填充一个一维数组 dp，以记录凑成每个金额所需的最少硬币数量。最终，返回 dp[amount] 的值，如果无法凑成总金额则返回 -1。

 c++代码

以下是C++的代码实现，使用动态规划来找到可以凑成总金额所需的最少硬币数量：

#include <vector>class Solution {
public:int coinChange(std::vector<int>& coins, int amount) {std::vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for (int coin : coins) {for (int i = coin; i <= amount; i++) {if (dp[i - coin] != INT_MAX) {dp[i] = std::min(dp[i], dp[i - coin] + 1);}}}return (dp[amount] == INT_MAX) ? -1 : dp[amount];}
};