给你一个整数数组 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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1,amount + 1);
dp[0] = 0;
for(int c : coins){
for(int i = c; i <= amount; i++){
dp[i] = min(dp[i], dp[i - c] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};vector<int> dp(amount + 1, amount + 1);
创建一个 dp 数组，大小为 amount + 1。dp[i] 表示组成金额 i 所需的最少硬币数。
由于我们要找一个最小值，所以初始化所有 dp[i] 为 amount + 1，因为coin>=1，不可能会有这个值，但这可以表示我们还没有找到一个解。
for (int coin : coins)：
对每一个硬币 coin，我们遍历从 coin 到 amount 的所有金额 i，更新 dp[i]（小于coin的不成立）
for (int i = coin; i <= amount; i++)：
对于每个金额 i，我们可以选择将当前硬币 coin 添加到组成金额 i - coin 的解上，从而更新 dp[i] 为 dp[i] = min(dp[i], dp[i - coin] + 1)，表示最少硬币数的更新。
return dp[amount] > amount ? -1 : dp[amount];
如果 dp[amount] 仍然大于 amount，说明我们没有找到一个有效的解，因此返回 -1。