题目描述
LeetCode 322 — 零钱兑换 (Medium)
给你一个整数数组 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
求解思路
最直接的想法是贪心——每次尽量挑面值最大的硬币，剩下的金额再继续凑。但贪心会翻车：coins = [1,5,11]、amount = 15 时，贪心先拿 11，剩下 4 只能用四枚 1，一共 5 枚；而最优解是 5+5+5，只要 3 枚。所以这条路走不通。
换个角度看：凑出金额 j 的最优解，一定可以由凑出某个金额 j - c 的最优解再加一枚面值为 c 的硬币得到。也就是说，如果已经知道所有比 j 小的金额分别需要多少枚硬币，那么 j 的答案就是把每种面值都试一遍，取 dp[j-c] + 1 的最小值。这个式子本身说明了最优子结构——大金额的最优解由小金额的最优解拼接而来，也自然指向动态规划。
设 dp[j] 为凑出金额 j 所需的最少硬币数，从小到大依次推出每个金额。初始时 dp[0] = 0，凑出 0 元不需要任何硬币；其余位置全部置为 INT_MAX，表示这个金额暂时凑不出来。转移时，如果 dp[j-c] 还是 INT_MAX，说明 j-c 本身凑不出，再加一枚 c 也凑不出 j，直接跳过；否则用 dp[j-c] + 1 更新 dp[j]。
遍历顺序值得一提：外层枚举每种硬币、内层让 j 从小到大递增。因为每种硬币可以无限使用，内层正序意味着同一枚硬币的遍历中，刚刚算出的 dp 值马上能被后面更大的金额复用——这正是完全背包的经典循环顺序。至于面值超过 amount 的硬币，内层循环从一开始就不会进入，自然被忽略；amount 为 0 时答案是 dp[0] = 0。最后看 dp[amount]：仍是 INT_MAX 说明凑不出，返回 -1，否则返回它的值。
解法：动态规划
/*
设dp(j)为凑出金额为i的最小硬币数
dp(j) = min{ dp( j - coins(i) ) + 1 } if dp( j - coins(i) ) != INT_MAX
初始化dp = INT_MAX; dp(0) = 0
*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1,INT_MAX);
dp[0] = 0;
for(int i = 0; i < coins.size(); i++){
for(int j = coins[i]; j <= amount; j++){
if(dp[j - coins[i]] == INT_MAX) continue;
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] != INT_MAX ? dp[amount] : -1;
}
};
复杂度： 时间 O(n × amount)，n 为硬币种数，每个金额都要用每种硬币尝试一次；空间 O(amount)，仅一个长度为 amount + 1 的 dp 数组。
相关题目
- LeetCode 518 — 零钱兑换 II（同样是完全背包，求的是组合数）
- LeetCode 279 — 完全平方数（硬币面值变成平方数）
- LeetCode 377 — 组合总和 Ⅳ
- LeetCode 983 — 最低票价