零钱兑换：最少几枚，凑不出给 -1
硬币无限枚。凑金额 a 时枚举最后一枚是哪种面额，剩下 a−c 查表。问的是枚数，不是有多少种组合；永远凑不出就返回 -1。
dp[0]=0，其余先标成到不了。对每个金额 a，尝试每枚 c≤a，取 dp[a−c]+1 的最小。结束时若仍到不了，返回 -1。时间 O(amount×硬币种数)，空间 O(amount)。
给你若干面额的硬币和一个金额 amount。每种面额都能用无限枚，求凑出这个金额最少要几枚。任何一种凑法都凑不出，返回 -1。
主例 coins = [1, 2, 5]，amount = 11。一种最少凑法是 5+5+1，三枚。5+2+2+2 是四枚，更差。答案是 3。
这道题不是 LC518。518 问有多少种组合，本题问最少枚数。本文要回答：为什么贪心先用大面额会错，主例表上 5、10、11 三个格子怎么来，以及「到不了」怎样一直传到答案的 -1。
逐金额枚举最后一枚
第一直觉是能用大的就用大的。主例 11 先扣 5 再扣 5 再扣 1，碰巧是对的。换成 coins=[1,3,4]、amount=6：贪心会拿 4+1+1 共三枚，可是 3+3 只要两枚。大面额不是永远更优。枚举所有组合能做对，但同一段剩余金额会被算许多遍。
缺的是按金额从小到大记「最少几枚」。dp[a] 表示凑出 a 的最少枚数。最后一枚一定是某种面额 c，且 c≤a，剩下 a−c 的最少枚数已经在表里，所以 dp[a] = min(dp[a−c]) + 1。dp[0]=0：凑 0 不需要硬币。某个 a 对所有硬币都加不出，就保持「到不了」，最后若 dp[amount] 仍是到不了，返回 -1。
硬币可重复用，因为子问题还可以再选同样的 c。这是完全背包的最少件数，不是 518 那种「方案数相加」。转移用 min 而不是加，初始化用无穷而不是 0，两处写反就会把本题做成另一题。
用手走主例。金额 1 只能用 1，dp[1]=1。金额 2 用一枚 2 比两枚 1 更少，dp[2]=1。金额 3、4 分别是 2、2。金额 5 第一次能用 5，dp[0]+1=1，演示停在这里。
金额 10 用两枚 5，dp[5]+1=2。金额 11 看三枚硬币：减 1 看 dp[10]=2，减 2 看 dp[9]=3，减 5 看 dp[6]=2，加一后最小是 3。整表 [0,1,1,2,2,1,2,2,3,3,2,3]，答案 3，对应 5+5+1。
若硬币是 [2,4]、金额 3，从 1 到 3 没有任何一格能从 0 走过来，dp[3] 一直是无穷，返回 -1。不要把到不了的格子写成 0：0 只属于金额 0，否则 min 会误以为「零枚就能凑出 3」。也不要在表里数组合种数——主例凑 11 的组合不止一种，题目只要 3 这个枚数。
金额从 1 加到 amount，保证 a−c 已经算完。每种金额看一遍所有硬币，时间与金额乘币种成正比。空间只留一排金额。面试时先说清「最少枚数、无解 -1」，再写转移，避免一上手按 518 去累加。
与贪心的区别面额不成倍数时，先用大的可能更亏，[1,3,4] 凑 6 就是反例。DP 把每一种「最后一枚」都试一遍。和 518 的差别：这里取 min 求枚数，那里做加法求组合数。
Go：DP 最小化
func coinChange(coins []int, amount int) int {const INF = 1 << 30dp := make([]int, amount+1)for i := range dp { dp[i] = INF }dp[0] = 0for a := 1; a <= amount; a++ {for _, c := range coins {if c <= a && dp[a-c]+1 < dp[a] {dp[a] = dp[a-c] + 1}}}if dp[amount] >= INF { return -1 }return dp[amount]}
1INF 表示到不了。只有 dp[0] 是 0。格子保持 INF，最后才能正确返回 -1。
2c≤a 才读 dp[a-c]，避免负下标。主例 a=11 比较的是 10、9、6 三格，最小加一得 3。
3判断用 >= INF 而不是 ==，防止 INF+1 溢出后比较异常。返回的是枚数，不要在这里累加方案数。
总结
枚举最后一枚硬币取最小；到不了返回 -1。主例 11 用三枚。不是组合数。
- 贪心在 [1,3,4] 凑 6 上会输给 3+3。每种最后一枚都要试。
- 主例 dp[5]=1、dp[10]=2、dp[11]=3，对应 5+5+1。
- 初始化无穷、转移用 min。写成 0 和加法就变成 518 的组合数。