给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
j解:这题有两种解法，回溯法和动态规划
动态规划
我们采用自下而上的方式进行思考。仍定义 F(i)F(i) 为组成金额 ii 所需最少的硬币数量，假设在计算 F(i)F(i) 之前，我们已经计算出 F(0)-F(i-1)F(0)−F(i−1) 的答案。 则 F(i)F(i) 对应的转移方程应为
F(i)=minF(i−cj)+1
其中 cj代表的是第 jj 枚硬币的面值，即我们枚举最后一枚硬币面额是 cj
那么需要从 i-cj
这个金额的状态 F(i-cj)
转移过来，再算上枚举的这枚硬币数量 11 的贡献，由于要硬币数量最少，所以 F(i)为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。
通过这道题
这里插一下动态规划里最重要的状态转移
「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
f(n) = /begin{cases} 1, n = 1, 2 // f(n – 1) + f(n – 2), n > 2 /end{cases}
f(n)={
1,n=1,2
f(n−1)+f(n−2),n>2
//////////////////////////////////////
为啥叫「状态转移方程」？为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n – 1 和状态 n – 2 相加转移而来，这就叫状态转移，仅此而已。
你会发现，上面的几种解法中的所有操作，例如 return f(n – 1) + f(n – 2)，dp[i] = dp[i – 1] + dp[i – 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。很容易发现，其实状态转移方程直接代表着暴力解法。
///////////////////////////////////////
class Solution { public: int coinChange(vector<int>& coins, int amount) { int MAX=amount+1; vector<int> vec(amount+1,MAX); vec[0]=0; //f(n)=f(n-coins[i])+1; for(int i=1;i<=amount;i++) { for(int j=0;j<coins.size();j++) { //当前币值比要求的第i个最小货币数都大，因为货币最小为1，可以跳过 if(i-coins[j]<0) { continue; } vec[i]=min(vec[i],vec[i-coins[j]]+1); } } return vec[amount]>amount?-1:vec[amount]; } };
下面这个介绍回溯，我最开始也是回溯做的，但是在个别测试用例中超时，看一下别人做的。把某些情况快速跳过，会很快。
解题思路
贪心
11. 想要总硬币数最少，肯定是优先用大面值硬币，所以对 coins 按从大到小排序
12. 先丢大硬币，再丢会超过总额时，就可以递归下一层丢的是稍小面值的硬币
乘法对加法的加速
21. 优先丢大硬币进去尝试，也没必要一个一个丢，可以用乘法算一下最多能丢几个
k = amount / coins[c_index] 计算最大能投几个
amount – k * coins[c_index] 减去扔了 k 个硬币
count + k 加 k 个硬币
如果因为丢多了导致最后无法凑出总额，再回溯减少大硬币数量
最先找到的并不是最优解
31. 注意不是现实中发行的硬币，面值组合规划合理，会有奇葩情况
32. 考虑到有 [1,7,10] 这种用例，按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到
33. 所以还是需要把所有情况都递归完
ans 疯狂剪枝
41. 贪心虽然得不到最优解，但也不是没用的
42. 我们快速算出一个贪心的 ans 之后，虽然还会有奇葩情况，但是绝大部分普通情况就可以疯狂剪枝了
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/17558.html