#322
中等
中频
动态规划零钱兑换
这是一道围绕数组展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你若干种硬币面额，每种硬币都可以无限使用。
要求你凑出总金额 amount，并返回所需硬币数量的最小值。如果凑不出来，就返回 -1。
一句话概括：
用最少数量的硬币，去拼出目标金额。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用一维 DP 维护凑出每个金额所需的最少硬币数，状态转移来自“最后一枚硬币选什么”。
推荐代码
推荐解法：动态规划
时间复杂度： O(amount * n)
空间复杂度： O(amount)
核心思路： 用一维 DP 维护凑出每个金额所需的最少硬币数，状态转移来自“最后一枚硬币选什么”。
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 i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用一维 DP，把每个金额的最少硬币数当成状态。
核心过程
- 定义
dp[i]表示凑出金额i的最少硬币数。 - 初始化
dp[0] = 0，其余设为不可达大值。 - 对每个金额尝试所有硬币，做
dp[i] = min(dp[i], dp[i-coin] + 1)转移。 - 最后如果
dp[amount]仍不可达，就返回-1，否则返回最优值。
复杂度总结
时间复杂度 O(amount * n)，空间复杂度 O(amount)。
面试补一句：这题高频误区是误用贪心，记住它本质是完全背包最小值。
核心思路
零钱兑换的本质是完全背包最小值问题。对每个金额，都尝试把某枚硬币作为最后一枚，看看能否由更小金额转移过来。
步骤讲解
1
初始化 DP 数组
设 dp[i] 表示凑出金额 i 的最少硬币数，初始设成一个不可能的大值，dp[0] = 0。
为什么这样做：只有金额 0 不需要硬币，其他状态都要靠转移更新。
对应代码提示：Arrays.fill(dp, amount + 1); dp[0] = 0;
2
枚举金额和硬币做转移
对每个金额 i，尝试每个硬币 coin，若 i-coin 可达，就更新 dp[i]。
为什么这样做：当前金额的最优解，来自某个更小金额的最优解加上一枚硬币。
对应代码提示：dp[i] = Math.min(dp[i], dp[i - coin] + 1);
3
根据最终状态返回结果
如果 dp[amount] 仍是初始大值，说明无法凑出目标金额；否则返回它。
为什么这样做：并非所有金额都一定可达，不能直接返回数组值。
对应代码提示：return dp[amount] > amount ? -1 : dp[amount];
易错点
把不可达状态也参与转移
会导致无意义的大值继续传播，甚至溢出。
正确理解：用
amount + 1 这类安全哨兵值，并在更新时注意前态可达。把这题写成贪心
硬币面额不满足特殊条件时，贪心选最大面额不一定最优。
正确理解：优先按最优子结构做 DP。
忘记处理凑不出的情况
最终状态可能仍然保持初始大值，不是合法答案。
正确理解：结束后判断是否仍大于
amount，若是则返回 -1。复杂度与适用判断
时间复杂度：O(amount * n)
空间复杂度：O(amount)
比其他方案更好在哪里：比暴力 DFS 枚举所有组合稳定很多，也不依赖面额满足贪心条件。
适用判断：“最少个数凑目标值”这类题，通常都可以先往完全背包 DP 上靠。
额外提醒
- 这题问的是最少硬币数，不是方案数，所以转移用
min。