C++代码杂货店老板的小抽屉里有一堆不同面值的硬币，在给顾客找零时他习惯去凑成总金额所需的最少的硬币个数。你能不能写个程序帮他实现，若凑不出则返回-1。 【样例】 输入： coins：1,2,5 amount：11 输出： 3 11=5+5+1

思路：动态规划

定义状态：dp[i] 表示凑成金额 i 所需的最少硬币个数。

状态转移方程：dp[i] = min(dp[i], dp[i - coins[j]] + 1)，其中 coins[j] 表示第 j 个硬币的面值。

初始状态：dp[0] = 0，表示凑成金额为 0 不需要硬币。

最终答案：dp[amount]，表示凑成总金额所需的最少硬币个数。

如果 dp[amount] 仍为初始值，说明无法凑出总金额，返回 -1。

时间复杂度：O(amount*n)，其中 n 表示硬币的个数。

代码实现：

int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (i >= coins[j]) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}