322. 零钱兑换
一句话套路完全背包求最少硬币(贪心必错)
题目描述
给你一个整数数组 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
思路
时间
O(amount·|coins|)空间
O(amount)状态
dp[a] = 凑出金额 a 所需的最少硬币数;凑不出记为 -1(这里用 BIG 哨兵)。
转移
完全背包 —— 枚举最后一枚硬币 c:dp[a] = min(dp[a-c]+1)。
为什么不能用贪心
coins=[1,3,4], amount=6,贪心 4+1+1=3 枚,最优 3+3=2 枚。
易错
dp[0]=0;结果判 dp[amount] 是否仍为哨兵;内层正序(硬币可重复使用)。
变体
Q518 求「组合数」-> 外层硬币、内层金额,累加;Q377 排列数 -> 内外层互换。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0322 {
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int BIG = amount + 1; // 比任何合法解都大,等价于无穷
vector<int> dp(amount + 1, BIG);
dp[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
return dp[amount] == BIG ? -1 : dp[amount];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0322::Solution s;
vector<int> a{1, 2, 5};
CHECK_EQ(s.coinChange(a, 11), 3); // 5+5+1
vector<int> b{2};
CHECK_EQ(s.coinChange(b, 3), -1); // 凑不出
vector<int> c{1};
CHECK_EQ(s.coinChange(c, 0), 0);
vector<int> d{1, 3, 4}; // 反例:贪心会给出 3,正确答案是 2
CHECK_EQ(s.coinChange(d, 6), 2);
vector<int> e{2, 5};
CHECK_EQ(s.coinChange(e, 5), 1); // 恰好一枚
CHECK_EQ(s.coinChange(e, 4), 2);
CHECK_EQ(s.coinChange(e, 3), -1);