这道题是经典的一维动态规划问题，题目要求：给定硬币面额数组 coins 和总金额 amount，用最少的硬币数凑出这个金额，如果无法凑出则返回 -1。leetcode
看起来像是「完全背包」的变体，但真正写代码时，很多细节非常容易出错，比如初始值、dp[0] 的含义、不可达状态怎么表示等。leetcode+1
本文从一个"接近正确但有 bug 的思路"出发，一步步推导出正确的 DP 解法和代码实现。
题意与状态定义
题目原文要点如下：leetcode
- 给你一个整数数组 coins，表示不同面额的硬币。
- 给你一个整数 amount，表示总金额。
- 返回凑成总金额所需的 最少 硬币数；如果无法凑成，返回 -1。
- 每种硬币的数量可以视为 无限。
自然的状态定义是：
定义 dp[i]：凑出金额 i 所需的最少硬币个数。
在这个定义下，有一个特别关键的点：
凑出金额 0 不需要任何硬币，所以dp[0] = 0是唯一合理的取值。
如果把 dp[0] 设成 1，就会出现：
dp[coin] = min(dp[coin], dp[0] + 1)这时 dp[coin] 会被更新为 2，意味着凑一个 coin 面额需要两枚硬币，这显然不符合题意。
初始化与"不可达状态"
有了状态定义，就要考虑「还没被凑出来」的金额怎么表示。常见错误是：
- 把所有 dp[i] 初始化成 0，然后依赖转移去堆加。
- 或者用 INT_MAX 之类的值，但在 dp[i - coin] + 1 时不考虑溢出或不可达的问题。
更安全、易理解的方式是：
- 将所有 dp[i] 初始化为一个「不可能达到的上界」，比如amount + 1。
- 因为最多用 amount 枚面额为 1 的硬币，所以 amount + 1 一定是无效解。
- 再设置 dp[0] = 0，表示金额 0 只需要 0 枚硬币。
在 C 代码中也可以用 INF_MAX 表示不可达，然后在转移时跳过不可达状态。leetcode
示例（C 代码中的初始化方式）：leetcode
- 使用宏定义一个无限大值：#define INF_MAX 0x7fffffff。leetcode
- 分配数组之后，将 dp[0…amount] 全部赋值为 INF_MAX。leetcode
- 再单独令 dp[0] = 0。leetcode
这样，当某个金额 i 当前还凑不出来时，dp[i] 就会保持为 INF_MAX，在做转移时可以通过判断是否等于 INF_MAX 来避免错误使用这个状态。leetcode
转移方程与遍历顺序
在一维 DP 下，标准的转移方程是：
对于每个金额 i（1 到 amount）：
- 遍历每个硬币 coin：
- 如果 i - coin >= 0 且 dp[i - coin] 可达，那么：
- dp[i] = min(dp[i], dp[i - coin] + 1)。
- 如果 i - coin >= 0 且 dp[i - coin] 可达，那么：
注意这里有几个细节容易出错：
不能只遍历"大于当前 i 的 coin"
只有 coin <= i 的时候，才能用于凑金额 i。
所以代码中通常写成：if (i - coin < 0) continue;。leetcode
必须跳过不可达状态
如果 dp[i - coin] 还是初始化的「INF」，说明金额 i - coin 根本凑不出来。
此时不能做 dp[i - coin] + 1，否则会以"垃圾值"去更新 dp[i]。
C 代码中通过：
if (dp[i - choice] == INF_MAX) continue;来规避。leetcode
遍历顺序
这里外层是金额 i，内层是硬币 coins[j]，属于典型的一维完全背包写法之一：leetcode
for i in [1..amount] for each coin因为每个硬币可以重复使用，所以不会因为遍历顺序而导致错过组合。
最终答案与返回值处理
当所有状态都计算完之后，答案在 dp[amount] 中：
- 如果 dp[amount] 仍然是初始化的「INF」（或者 amount + 1），说明无法凑出该金额，返回 -1。
- 否则，返回 dp[amount] 即可。
在实际 C 实现中，代码形态如下（与你提交的版本一致）：leetcode
- 用 INF_MAX 初始化所有 dp[i]。leetcode
- 更新完所有状态后，通过：
得到最终答案。leetcoderet = dp[amount] == INF_MAX ? -1 : dp[amount]; - 最后记得 free(dp)，防止内存泄漏。leetcode
完整 C 实现解析
下面是一份通过 LeetCode 所有测试用例的 C 代码，它完整体现了上面所有的思路要点：leetcode
#include<stdlib.h>#defineINF_MAX0x7fffffff#defineMIN(a,b)((a)<(b)?(a):(b))intcoinChange(int*coins,intcoinsSize,intamount){inti,j,choice,ret;int*dp=NULL;dp=(int*)malloc((amount+1)*sizeof(int));for(i=0;i<=amount;i++)dp[i]=INF_MAX;// 初始化为不可达状态dp[0]=0;// 凑出金额 0 需要 0 枚硬币for(i=1;i<=amount;i++){for(j=0;j<coinsSize;j++){choice=coins[j];if(i-choice<0)// 当前硬币面值比金额大，跳过continue;if(dp[i-choice]==INF_MAX)// 子状态不可达，跳过continue;dp[i]=MIN(dp[i],dp[i-choice]+1);// 状态转移}}ret=dp[amount]==INF_MAX?-1:dp[amount];// 处理答案free(dp);returnret;}这段代码的关键点可以归纳为：
- 状态定义清晰：dp[i] 表示金额 i 的最少硬币数。
- 初始化严谨：不可达用 INF_MAX 表示，dp[0] = 0。
- 转移安全：只有在子状态可达的前提下才尝试更新。
- 返回值合理：判断最终状态是否可达，决定返回 -1 还是 dp[amount]。
面试思路复盘：面试官会怎么问你
如果在面试中现场推这个题，面试官可能会围绕如下几个问题引导你修正思路：
- 「你能用一句话准确定义 dp[i] 吗？」
- 「当 amount = 0 时答案是多少？那 dp[0] 应该怎么初始化？」
- 「还没被凑出来的金额，你准备用什么值表示？」
- 「什么时候可以安全地做 dp[i - coin] + 1？」
- 「在计算 dp[i] 时，哪些面额的 coin 对它是有效的？遍历条件是什么？」
只要你能把这些问题回答清楚，基本就已经掌握了这道题的核心思路，代码也就顺理成章写出来了。
总结
如果你愿意，可以把你之后写的别的语言版本（比如 C++/Java/Python）也贴出来，再对照这个 DP 模板做一次统一整理，顺便形成一套自己的「完全背包最少数量」模板。
https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150
https://leetcode.com/problems/coin-change/submissions/1870566313/?envType=study-plan-v2&envId=top-interview-150
