高雄市网站建设_网站建设公司_导航易用性_seo优化

这道题是经典的一维动态规划问题，题目要求：给定硬币面额数组 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 时不考虑溢出或不可达的问题。

更安全、易理解的方式是：

1. 将所有 dp[i] 初始化为一个「不可能达到的上界」，比如amount + 1。
2. 因为最多用 amount 枚面额为 1 的硬币，所以 amount + 1 一定是无效解。
3. 再设置 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"

只有 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​
• 更新完所有状态后，通过：

  ret = dp[amount] == INF_MAX ? -1 : dp[amount];

  得到最终答案。leetcode​
• 最后记得 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;}

这段代码的关键点可以归纳为：

1. 状态定义清晰：dp[i] 表示金额 i 的最少硬币数。
2. 初始化严谨：不可达用 INF_MAX 表示，dp[0] = 0。
3. 转移安全：只有在子状态可达的前提下才尝试更新。
4. 返回值合理：判断最终状态是否可达，决定返回 -1 还是 dp[amount]。

面试思路复盘：面试官会怎么问你

如果在面试中现场推这个题，面试官可能会围绕如下几个问题引导你修正思路：

1. 「你能用一句话准确定义 dp[i] 吗？」
2. 「当 amount = 0 时答案是多少？那 dp[0] 应该怎么初始化？」
3. 「还没被凑出来的金额，你准备用什么值表示？」
4. 「什么时候可以安全地做 dp[i - coin] + 1？」
5. 「在计算 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