322. 零钱兑换
题目描述
输入一个整数数组 coins，表示若干种不同面额的硬币，以及一个整数 amount，表示要凑出的总金额。每种硬币都可以无限次使用。
返回凑出 amount 最少需要多少枚硬币。不管怎么组合都凑不出时返回 -1。
示例 1
输入：coins = [1,2,5], amount = 11 输出：3
解释：11 = 5 + 5 + 1，共 3 枚。
示例 2
输入：coins = [2], amount = 3 输出：-1
解释：只有面额 2，无法凑出奇数 3。
示例 3
输入：coins = [1], amount = 0 输出：0
解释：金额为 0，不需要硬币。
数据范围
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
解题思路：完全背包动态规划
dp[x] 表示金额 x 的最少硬币数，逐个尝试最后放入的硬币。
为什么正确
dp[x] 是所有已考虑硬币组合中的最优值，且转移只依赖更小金额。
复杂度分析
时间 O(amount×len(coins))，空间 O(amount)。
易错点
外层按金额递增允许硬币无限重复；返回前要把不可达的哨兵值转成 -1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
for coin in coins:
if coin <= x:
dp[x] = min(dp[x], dp[x - coin] + 1)
return -1 if dp[amount] > amount else dp[amount]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 x = 1; x <= amount; x++) {
for (int coin : coins) {
if (coin <= x) {
dp[x] = Math.min(dp[x], dp[x - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int x = 1; x <= amount; x++) {
for (int coin : coins) {
if (coin <= x) {
dp[x] = min(dp[x], dp[x - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp {
dp[i] = amount + 1
}
dp[0] = 0
for x := 1; x <= amount; x++ {
for _, coin := range coins {
if coin <= x {
dp[x] = min(dp[x], dp[x-coin]+1)
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}var coinChange = function(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let x = 1; x <= amount; x++) {
for (const coin of coins) {
if (coin <= x) {
dp[x] = Math.min(dp[x], dp[x - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};function coinChange(coins: number[], amount: number): number {
const dp: number[] = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let x = 1; x <= amount; x++) {
for (const coin of coins) {
if (coin <= x) {
dp[x] = Math.min(dp[x], dp[x - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};其他解法
DP 按金额从小到大填表，每个金额枚举最后一枚硬币；BFS 按硬币个数分层扩展可达金额。两者都保证每个金额只处理一次，只是一个是递推视角，一个是最短路视角。
解法 2：广度优先搜索 时间 O(S·k)，空间 O(S)
把 0 到 amount 的每个金额看成图上的点，金额 x 加上一枚硬币到达 x + coin。从 0 出发做 BFS，每层代表多用一枚硬币，第一次到达 amount 时的层数就是最少硬币数；队列取空仍未到达则返回 -1。超过 amount 或已访问的金额不再入队。
把“最少硬币数”看成无权图最短路，答案较小时能提前停止。最坏情况和 DP 相同，还需要队列和访问数组；只能求最小值，不像 DP 那样能改成计数（第 518 题）。
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
visited = [False] * (amount + 1)
visited[0] = True
level = [0]
steps = 0
while level:
steps += 1
nxt = []
for x in level:
for c in coins:
y = x + c
if y == amount:
return steps
if y < amount and not visited[y]:
visited[y] = True
nxt.append(y)
level = nxt
return -1class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
boolean[] visited = new boolean[amount + 1];
visited[0] = true;
List<Integer> level = new ArrayList<>();
level.add(0);
int steps = 0;
while (!level.isEmpty()) {
steps++;
List<Integer> nxt = new ArrayList<>();
for (int x : level) {
for (int c : coins) {
long y = (long) x + c;
if (y == amount) return steps;
if (y < amount && !visited[(int) y]) {
visited[(int) y] = true;
nxt.add((int) y);
}
}
}
level = nxt;
}
return -1;
}
}class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
vector<char> visited(amount + 1, 0);
visited[0] = 1;
vector<int> level{0};
int steps = 0;
while (!level.empty()) {
steps++;
vector<int> nxt;
for (int x : level) {
for (int c : coins) {
long long y = (long long)x + c;
if (y == amount) return steps;
if (y < amount && !visited[y]) {
visited[y] = 1;
nxt.push_back((int)y);
}
}
}
level.swap(nxt);
}
return -1;
}
};func coinChange(coins []int, amount int) int {
if amount == 0 {
return 0
}
visited := make([]bool, amount+1)
visited[0] = true
level := []int{0}
steps := 0
for len(level) > 0 {
steps++
nxt := []int{}
for _, x := range level {
for _, c := range coins {
y := x + c
if y == amount {
return steps
}
if y < amount && !visited[y] {
visited[y] = true
nxt = append(nxt, y)
}
}
}
level = nxt
}
return -1
}var coinChange = function(coins, amount) {
if (amount === 0) return 0;
const visited = new Uint8Array(amount + 1);
visited[0] = 1;
let level = [0];
let steps = 0;
while (level.length) {
steps++;
const nxt = [];
for (const x of level) {
for (const c of coins) {
const y = x + c;
if (y === amount) return steps;
if (y < amount && !visited[y]) {
visited[y] = 1;
nxt.push(y);
}
}
}
level = nxt;
}
return -1;
};function coinChange(coins: number[], amount: number): number {
if (amount === 0) return 0;
const visited = new Uint8Array(amount + 1);
visited[0] = 1;
let level: number[] = [0];
let steps = 0;
while (level.length) {
steps++;
const nxt: number[] = [];
for (const x of level) {
for (const c of coins) {
const y = x + c;
if (y === amount) return steps;
if (y < amount && !visited[y]) {
visited[y] = 1;
nxt.push(y);
}
}
}
level = nxt;
}
return -1;
}