322. 零钱兑换 Medium
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2:
输入：coins = [2], amount = 3
输出：-1
示例 3:
输入：coins = [1], amount = 0
输出：0
解题思路
输入： 一个整数数组 coins，一个整数 amount
输出： 返回可以凑成总金额 amount 的最少硬币个数，如果凑不出则返回 -1
本题属于0-1 背包 + 计数型DP问题。
本题有多种解法分别是：
- 记忆化递归（DFS + 缓存）
- 一维 DP
解法一：记忆化搜索（递归 + 缓存）
思路：
- 函数
dfs(amount)表示：凑出金额amount需要的最少硬币数 - 对于每个硬币
coin，尝试从amount - coin去递归求解 - 使用
memo字典记住已经算过的结果
解法二：一维 DP
状态定义：
dp[i]表示凑出金额i所需的最少硬币数
转移方程：
dp[i] = min(dp[i], dp[i - coin] + 1)，其中coin遍历coins中所有能用的硬币
初始化：
dp[0] = 0（金额为 0 时不需要硬币）- 其他
dp[i] = inf表示初始无法凑出
代码实现
解法一：记忆化搜索（递归 + 缓存）
python
from typing import List
from functools import cache
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
# 使用缓存加速递归，避免重复计算
@cache
def dfs(i: int, c: int) -> int:
# 如果没有硬币可用
if i < 0:
return 0 if c == 0 else float('inf') # 如果目标金额为0，则需要0枚硬币；否则无法凑出，返回正无穷
if c < 0:
return float('inf') # 金额为负数，说明非法，返回正无穷
# 不选当前硬币 or 选择当前硬币（注意dfs(i, c - coins[i])表示可以重复使用当前硬币）
return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
# 从最后一个硬币开始尝试凑出amount
ans = dfs(n - 1, amount)
return ans if ans != float('inf') else -1 # 如果无法凑出目标金额，返回-1javascript
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
const cache = new Map();
function dfs(i, c) {
if (i < 0)
return c == 0 ? 0 : Infinity;
if (cache.get(`(${i}, ${c})`))
return cache.get(`(${i}, ${c})`);
let ans;
if (c < coins[i])
ans = dfs(i - 1, c)
else {
ans = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
}
cache.set(`(${i}, ${c})`, ans);
return ans;
}
const ans = dfs(coins.length - 1, amount);
return ans < Infinity ? ans : -1;
};解法二：一维 DP
python
from typing import List
from functools import cache
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
# 初始化dp数组，f[c]表示凑出金额c所需的最少硬币数
# 初始值设为正无穷，表示一开始都无法凑出
f = [float('inf')] * (amount + 1)
# 凑出金额0只需要0个硬币
f[0] = 0
# 遍历每个硬币面值
for x in coins:
# 更新所有 >= x 的金额
for c in range(x, amount + 1):
# 状态转移：是否选择当前硬币 x
# 如果选择了，f[c] 可以从 f[c - x] + 1 转移过来
f[c] = min(f[c], f[c - x] + 1)
ans = f[amount]
# 如果f[amount] 还是无穷，说明无法凑出目标金额，返回 -1
return ans if ans < float('inf') else -1javascript
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let x of coins) {
for (let c = x; c < amount + 1; c++) {
dp[c] = Math.min(dp[c], dp[c - x] + 1);
}
}
const ans = dp[amount];
return ans < Infinity ? ans : -1;
};复杂度分析
时间复杂度：O(n)
空间复杂度：
- 记忆化搜索（递归 + 缓存）：O(n)
- 一维 DP：O(1)