零钱兑换
进阶零钱兑换是"完全背包"变体，求最小硬币数。
// 算法讲解
零钱兑换
输入面额和目标金额（最后一个数），如 1,5,11,27。
待机
速度 中
待机 ⌨1int coinChange(vector<int>& coins, int amount) {
2 vector<int> dp(amount + 1, INT_MAX);
3 dp[0] = 0;
4 for (int c : coins)
5 for (int i = c; i <= amount; i++)
6 if (dp[i - c] != INT_MAX)
7 dp[i] = min(dp[i], dp[i - c] + 1);
8 return dp[amount] == INT_MAX ? -1 : dp[amount];
9}
复杂度分析
时间 O(n * amount)
空间 O(amount)
最优 O(n * amount)
最坏 O(n * amount)
算法讲解
给定若干面额的硬币和目标金额，求凑出该金额所需的最少硬币数。
dp[i] 表示金额 i 的最少硬币数，转移为 dp[i] = min(dp[i - coin] + 1) 对所有 coin <= i。
和 0-1 背包不同，每种硬币可以使用无限次，因此是完全背包的变体。
如果 dp[amount] 仍为初始值，说明无法凑出该金额。