英文原文
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3 Output: -1
Example 3:
Input: coins = [1], amount = 0 Output: 0
Example 4:
Input: coins = [1], amount = 1 Output: 1
Example 5:
Input: coins = [1], amount = 2 Output: 2
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
中文题目
给你一个整数数组 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
示例 4：
输入：coins = [1], amount = 1 输出：1
示例 5：
输入：coins = [1], amount = 2 输出：2
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
通过代码
高赞题解
2021.03.20 更新
因为本题确实不适合贪心思想，官方加入新用例后，原代码会超时
修改了代码，加入 cache ，但是时间也不会很快了，这与用例特点有关
加入用例前：dp 垃圾效率，看我贪心秒了
加入用例后：唯唯诺诺，还是 dp 香
现在用例还能苟过（0 <= amount <= $10^4$），量级再大一点可能就够呛，求放过
这里也看到力扣平台持续不断的补充用例，保证题目质量，点个赞
我已经被 hack 好几篇题解了 （T T）
提个小意见，希望在加入用例之后，可以想个办法把很早以前跑的代码时间更新了
现在 0ms 的记录还是这个思路的老代码，有些题目甚至还有 wa 的代码再前面
一年前写的“偷鸡“代码，还被评为精选题解，非常感谢大家的点赞和评论，不胜惶恐
虽然不是本题的正规解法，但是当做拓展思路的偏门解法，引发交流和思考可能也还大概还是有些意义吧
答题
[]class Solution { public: void coinChange(vector<int>& coins, int amount, int c_index, int count, int& ans) { if (amount == 0) { ans = min(ans, count); return; } if (c_index == coins.size()) return; if (vi[amount][c_index] <= count) return; for (int k = amount / coins[c_index]; k >= 0 && k + count < ans; k--) { int nextAmount = amount - k * coins[c_index]; coinChange(coins, nextAmount, c_index + 1, count + k, ans); } vi[amount][c_index] = min(vi[amount][c_index], count); } int coinChange(vector<int>& coins, int amount) { if (amount == 0) return 0; sort(coins.rbegin(), coins.rend()); int ans = INT_MAX; vi = vector<vector<int>>(amount + 1, vector<int>(coins.size(), INT_MAX)); coinChange(coins, amount, 0, 0, ans); return ans == INT_MAX ? -1 : ans; } private: vector<vector<int>> vi; };
原题解
思路
贪心
想要总硬币数最少，肯定是优先用大面值硬币，所以对
coins按从大到小排序先丢大硬币，再丢会超过总额时，就可以递归下一层丢的是稍小面值的硬币
乘法对加法的加速
- 优先丢大硬币进去尝试，也没必要一个一个丢，可以用乘法算一下最多能丢几个
k = amount / coins[c_index]计算最大能投几个amount - k * coins[c_index]减去扔了 k 个硬币count + k加 k 个硬币- 如果因为丢多了导致最后无法凑出总额，再回溯减少大硬币数量
最先找到的并不是最优解
注意不是现实中发行的硬币，面值组合规划合理，会有奇葩情况
考虑到有
[1,7,10]这种用例，按照贪心思路10 + 1 + 1 + 1 + 1会比7 + 7更早找到所以还是需要把所有情况都递归完
ans疯狂剪枝贪心虽然得不到最优解，但也不是没用的
我们快速算出一个贪心的
ans之后，虽然还会有奇葩情况，但是绝大部分普通情况就可以疯狂剪枝了
图解
[]void coinChange(vector<int>& coins, int amount, int c_index, int count, int& ans) { if (amount == 0) { ans = min(ans, count); return; } if (c_index == coins.size()) return; for (int k = amount / coins[c_index]; k >= 0 && k + count < ans; k--) { coinChange(coins, amount - k * coins[c_index], c_index + 1, count + k, ans); } } int coinChange(vector<int>& coins, int amount) { if (amount == 0) return 0; sort(coins.rbegin(), coins.rend()); int ans = INT_MAX; coinChange(coins, amount, 0, 0, ans); return ans == INT_MAX ? -1 : ans; }
执行时间
致谢
感谢您的观看，希望对您有帮助，欢迎热烈的交流！
如果感觉还不错就点个赞吧~
在 我的力扣个人主页 中有我使用的做题助手项目链接，帮助我收集整理题目，可以方便的 visual studio 调试，欢迎关注，star
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 331502 | 741481 | 44.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 最低票价 | 中等 |
