零钱兑换
给你一个整数数组 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] <= 2^31 - 10 <= amount <= 10^4
动态规划：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int INF = amount + 1;
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int i = 1; i <= amount; i++)
{
for (int coin : coins)
{
if (coin <= i && dp[i - coin] != INF)
{
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
};
核心思想
这题要求的是：用最少数量的硬币凑出 amount。
硬币可以无限次使用，所以它不是“每个硬币只能选一次”的问题，而是一个典型的完全背包问题。
不过这题不需要写成复杂的背包模板，可以直接从“最后一枚硬币是谁”这个角度理解。
假设现在要凑出金额 i。
如果最后一枚硬币的面额是 coin，那么前面已经凑出的金额一定是：
i - coin
如果凑出 i - coin 的最少硬币数是：
dp[i - coin]
那么再加上最后这枚 coin，凑出 i 的硬币数就是：
dp[i - coin] + 1
所以我们枚举所有可以作为最后一枚硬币的 coin，取最小值即可。
这题最关键的观察是：
凑出金额
i的最优方案，一定可以看成“凑出i - coin的最优方案 + 一枚面额为coin的硬币”。
状态定义
定义：
dp[i] 表示凑出金额 i 所需要的最少硬币个数。
题目要求的答案就是：
dp[amount]
如果某个金额无法凑出，就让它保持为一个很大的值 INF。
在代码中：
int INF = amount + 1;
因为所有硬币面额都是正整数。
如果金额 i 可以被凑出，那么即使全部使用面额为 1 的硬币，最多也只需要 i 枚。
因此对于 amount 范围内的问题，真正的答案不可能超过 amount。
所以 amount + 1 可以安全地表示“不可能凑出”。
递推公式推导
现在考虑如何计算 dp[i]。
对于每一种硬币面额 coin，如果：
coin <= i
那么这枚硬币可以作为凑出金额 i 的最后一枚硬币。
选择这枚硬币以后，剩余金额是：
i - coin
如果 i - coin 可以凑出，那么凑出 i 的一种方案就是：
dp[i - coin] + 1
其中 + 1 表示当前选择的这枚 coin。
由于最后一枚硬币可能是 coins 中的任意一种面额，所以要枚举所有硬币，取最小值：
dp[i] = min(dp[i], dp[i - coin] + 1)
完整条件是：
coin <= idp[i - coin]不是不可能状态
所以代码中写成：
if (coin <= i && dp[i - coin] != INF)
{
dp[i] = min(dp[i], dp[i - coin] + 1);
}
边界情况
当 amount = 0 时，不需要任何硬币就能凑出总金额 0。
所以：
dp[0] = 0
这也是整个递推的起点。
例如：
coins = [1], amount = 0
答案就是 0。
如果某个金额不能被任何组合凑出，它的 dp 值会一直保持为 INF。
最后如果：
dp[amount] == INF
说明没有方案可以凑出 amount，返回 -1。
为什么硬币可以重复使用
题目说每种硬币的数量是无限的。
在递推公式中：
dp[i] = min(dp[i], dp[i - coin] + 1)
dp[i - coin] 本身可能已经使用过面额为 coin 的硬币。
现在再额外加一枚 coin，仍然是合法的。
例如：
coins = [1, 2, 5], amount = 11
最优方案是：
11 = 5 + 5 + 1
其中面额 5 的硬币使用了两次。
这正是完全背包和普通 0-1 背包的区别：
0-1背包：每个物品最多只能用一次- 完全背包：每个物品可以使用无限次
本题属于完全背包。
为什么遍历顺序是正确的
代码中外层枚举金额：
for (int i = 1; i <= amount; i++)
内层枚举硬币：
for (int coin : coins)
当我们计算 dp[i] 时，只会用到：
dp[i - coin]
因为 coin >= 1，所以：
i - coin < i
也就是说，当前状态只依赖更小金额的状态。
而外层金额是从小到大遍历的，所以在计算 dp[i] 之前，所有可能用到的 dp[i - coin] 都已经计算完成。
因此这个递推顺序是正确的。
正确性证明
我们证明：动态规划算法返回的结果等于凑出 amount 所需的最少硬币个数；如果无法凑出，则返回 -1。
归纳基础
当金额为 0 时，不选择任何硬币就可以凑出。
所需硬币数量为 0，所以：
dp[0] = 0
正确。
归纳假设
假设对于所有小于 i 的金额 x，dp[x] 都已经正确表示凑出金额 x 所需的最少硬币数。
如果金额 x 无法凑出，那么 dp[x] 保持为 INF。
归纳推导
现在考虑金额 i。
任意一个凑出金额 i 的合法方案，最后一枚硬币一定来自数组 coins。
假设最后一枚硬币的面额是 coin。
那么最后一枚硬币之前，其余硬币凑出的金额一定是：
i - coin
并且必须满足：
coin <= i
根据归纳假设，dp[i - coin] 已经正确表示凑出 i - coin 的最少硬币数。
因此，在最后一枚硬币固定为 coin 的所有方案中，最少硬币数就是：
dp[i - coin] + 1
算法会枚举所有满足 coin <= i 的硬币，所以不会漏掉任何可能作为最后一枚硬币的选择。
因此，算法得到的最小值不会大于真实最优解。
另一方面，算法每次更新 dp[i] 时，使用的候选值都是：
dp[i - coin] + 1
这表示：
- 先用
dp[i - coin]枚硬币凑出金额i - coin - 再加入一枚面额为
coin的硬币
总金额就是：
i - coin + coin = i
所以算法构造出的每个候选方案都是真实合法的方案。
因此，算法得到的答案不会小于真实最优解。
综合两点可知，dp[i] 恰好等于凑出金额 i 所需的最少硬币数。
由数学归纳法可知，所有 0 <= i <= amount 的 dp[i] 都正确。
如果最终 dp[amount] 仍然是 INF，说明所有可能方案都无法凑出 amount，返回 -1 正确。
否则返回 dp[amount]，就是最少硬币数量。
因此算法正确。
举例理解
以：
coins = [1, 2, 5], amount = 11
为例。
初始化：
dp[0] = 0
逐步计算：
金额 i |
最优拆法 | dp[i] |
|---|---|---|
1 |
1 |
1 |
2 |
2 |
1 |
3 |
2 + 1 |
2 |
4 |
2 + 2 |
2 |
5 |
5 |
1 |
6 |
5 + 1 |
2 |
7 |
5 + 2 |
2 |
8 |
5 + 2 + 1 |
3 |
9 |
5 + 2 + 2 |
3 |
10 |
5 + 5 |
2 |
11 |
5 + 5 + 1 |
3 |
所以：
dp[11] = 3
最终答案是 3。
再看：
coins = [2], amount = 3
只能使用面额为 2 的硬币。
金额 1 无法凑出，金额 3 也无法由若干个 2 凑出。
所以 dp[3] 最终仍然是 INF，返回 -1。
复杂度分析
设硬币种类数为 m，目标金额为 amount。
外层循环枚举金额，从 1 到 amount。
内层循环枚举所有硬币，一共有 m 种。
所以时间复杂度是：
O(amount * m)
额外使用了一个长度为 amount + 1 的 dp 数组。
所以空间复杂度是：
`O(amount)