HHot 100C++ 图解

322. 零钱兑换

中等 动态规划(一维) 3 帧动画 在力扣上做

一句话套路完全背包求最少硬币(贪心必错)

题目描述

给你一个整数数组 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 <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= 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 排列数 -> 内外层互换。

图解

1 0 2 1 5 2
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp14 行
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];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q322_coin_change13 行
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);

↑↓ 选择↵ 打开/ 随时唤起