题目描述
给你一个整数数组 coins，表示不同面额的硬币；再给你一个整数 amount，表示总金额。
请你计算并返回：可以凑成总金额所需的最少硬币个数。 如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例分析
示例 1
输入: coins = [1,2,5], amount = 11
输出: 3
解释：
11 = 5 + 5 + 1
所以最少需要 3 枚硬币。
示例 2
输入: coins = [2], amount = 3
输出: -1
因为只有面额 2 的硬币，无论怎么选都凑不出 3，所以返回 -1。
示例 3
输入: coins = [1], amount = 0
输出: 0
总金额为 0，不需要任何硬币，所以答案是 0。
解题思路
这道题是一道非常经典的动态规划题，同时它也属于很典型的完全背包问题。
为什么说它是完全背包？
因为：
-
每种硬币可以选无限次
-
目标是凑出指定金额
-
同时希望“使用的硬币数量最少”
这正是完全背包模型的典型特征。
代码如下：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
这份代码非常标准，核心就在于：
dp[i]表示凑出金额i所需的最少硬币数。
状态定义
我们定义：
dp[i] = 凑出金额 i 所需的最少硬币数
这是整道题最核心的状态。
比如：
-
dp[0] = 0：凑出 0 元，不需要硬币 -
dp[1]：凑出 1 元最少需要几个硬币 -
dp[2]：凑出 2 元最少需要几个硬币 -
…
-
dp[amount]：就是最终答案
状态转移方程
假设当前我们正在考虑某个硬币面额：
coin
如果要凑金额 i，那么有两种可能：
-
不使用当前硬币 那么
dp[i]保持原来的值 -
使用一枚当前硬币 那么问题就变成：先凑出
i - coin，再加上这一枚硬币
于是状态转移就是：
dp[i] = min(dp[i], dp[i - coin] + 1)
含义非常直接：
-
dp[i]：原来凑出i的最优方案 -
dp[i - coin] + 1：先凑出i - coin，再用 1 枚当前硬币补到i
两者取最小值即可。
为什么这就是完全背包
在背包问题里：
-
如果每个物品只能选一次，就是 0/1 背包
-
如果每个物品可以选无限次，就是完全背包
而这里的每种硬币都可以无限次使用，所以就是完全背包。
对应到代码里，关键就在于这层循环：
for (int i = coin; i <= amount; i++)
这里 i 是从小到大遍历的。
为什么从小到大？
因为这样在更新 dp[i] 时，dp[i - coin] 可能已经在本轮用过当前硬币更新过了。 也就是说，当前硬币可以被重复使用，这正是完全背包的特征。
如果是 0/1 背包，通常就要从大到小遍历。
为什么初始化成 amount + 1
代码里有一句：
Arrays.fill(dp, amount + 1);
这一步很关键。
因为我们要求的是“最少硬币数”，所以一开始应该把每个状态初始化成一个不可能达到的很大值，表示：
目前还不知道怎么凑出来。
为什么取 amount + 1？
因为在最理想情况下，如果 coins 中有 1，那么凑出 amount 最多也只需要 amount 枚硬币。 所以 amount + 1 一定比任何合法答案都大，可以作为“无穷大”的替代值。
这样后面取 min 时就很方便。
为什么 dp[0] = 0
dp[0] = 0;
这表示：
凑出金额 0，不需要任何硬币。
这是动态规划的起点，也是所有后续转移的基础。
比如如果有硬币 coin = 2，那么更新 dp[2] 时会用到：
dp[2] = min(dp[2], dp[0] + 1)
也就是：
-
凑出 0 元需要 0 枚
-
再加一枚 2 元硬币
-
凑出 2 元需要 1 枚
所以 dp[0] = 0 是必须的。
代码解析
1. 定义 DP 数组
int[] dp = new int[amount + 1];
dp[i] 表示凑出金额 i 所需的最少硬币数。
2. 初始化为“大值”
Arrays.fill(dp, amount + 1);
表示一开始默认所有金额都不可达。
3. 初始化起点
dp[0] = 0;
凑出 0 元需要 0 枚硬币。
4. 遍历每一种硬币
for (int coin : coins) {
依次考虑每一种面额。
5. 遍历所有可以被更新的金额
for (int i = coin; i <= amount; i++) {
从 coin 开始，是因为小于 coin 的金额不可能通过当前硬币更新。
6. 状态转移
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
如果使用当前硬币，就相当于：
-
先凑出
i - coin -
再加一枚当前硬币
然后和原方案取最优。
7. 最后判断是否可达
return dp[amount] > amount ? -1 : dp[amount];
如果 dp[amount] 仍然比 amount 大，说明它从头到尾都没有被有效更新过，也就是无法凑出目标金额。
这时返回 -1。
否则返回最少硬币数。
示例推演
我们用：
coins = [1,2,5], amount = 11
来模拟一下。
初始时：
dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
这里 12 = amount + 1。
先处理硬币 1
因为 1 可以凑出所有金额，所以更新后：
dp = [0,1,2,3,4,5,6,7,8,9,10,11]
表示全部用 1 元硬币来凑。
再处理硬币 2
逐步更新后：
-
dp[2] = min(2, dp[0] + 1) = 1 -
dp[3] = min(3, dp[1] + 1) = 2 -
dp[4] = min(4, dp[2] + 1) = 2 -
…
最终会变成更优的结果，例如：
dp[10] = 5
表示 10 元可以用 5 枚 2 元硬币凑出。
再处理硬币 5
更新后：
-
dp[5] = min(3, dp[0] + 1) = 1 -
dp[10] = min(5, dp[5] + 1) = 2 -
dp[11] = min(6, dp[6] + 1) = 3
最终：
dp[11] = 3
也就是：
11 = 5 + 5 + 1
答案为 3。
为什么这题不能贪心
有些同学第一次做这题时，可能会想到贪心：
每次优先选最大的硬币。
但这种方法并不总是正确。
比如：
coins = [1,3,4], amount = 6
如果贪心：
-
先选 4，剩 2
-
再选 1，剩 1
-
再选 1，剩 0
总共用了 3 枚。
但最优解其实是：
3 + 3 = 6
只需要 2 枚。
所以这题不能用贪心，必须用动态规划去比较所有可能的组合。
和二维 DP 写法对比
这题也可以写成二维 DP：
dp[i][j] = 前 i 种硬币凑出金额 j 所需的最少硬币数
但二维写法会更占空间，而且这道题本身只依赖当前和之前状态，完全可以压缩成一维。
你这份代码已经是最经典、最简洁的一维完全背包写法了。
复杂度分析
设：
-
硬币种类数为
n -
目标金额为
amount
时间复杂度
O(n * amount)
因为每种硬币都要遍历一次金额区间。
空间复杂度
O(amount)
只使用了一个长度为 amount + 1 的一维数组。
这道题为什么经典
这题非常经典，因为它是“完全背包求最值”的代表题之一。
它训练的核心点有：
-
能不能识别出“每种物品可重复使用”这个特征
-
能不能正确写出状态定义
-
能不能理解一维 DP 的转移方向
-
能不能区分“求方案数”和“求最少个数”这两类背包题
所以这题不只是“零钱兑换”，更是完全背包模板题。
总结
这道题的核心可以概括成一句话：
dp[i]表示凑出金额i所需的最少硬币数，枚举每种硬币并尝试更新所有金额。
状态转移公式就是：
dp[i] = min(dp[i], dp[i - coin] + 1)
含义是：
-
不用当前硬币，保持原方案
-
用一枚当前硬币，从
i - coin转移过来
你可以把这题记成一句话：
零钱兑换就是“完全背包求最少物品数”模板题。
这是一道非常值得牢牢记住的动态规划经典题。
