LeetCode 题解工作台
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入： coins = [1, 2, 5] , am…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示使用前 种硬币，凑出金额 的最少硬币数。初始时 $f[0][0] = 0$，其余位置的值均为正无穷。 我们可以枚举使用的最后一枚硬币的数量 ，那么有：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 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
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解题思路
方法一：动态规划(完全背包)
我们定义 表示使用前 种硬币，凑出金额 的最少硬币数。初始时 ，其余位置的值均为正无穷。
我们可以枚举使用的最后一枚硬币的数量 ，那么有：
其中 表示第 种硬币的面值。
不妨令 ，那么有：
将二式代入一式，我们可以得到以下状态转移方程：
最后答案即为 。
时间复杂度 ，空间复杂度 。其中 和 分别为硬币的种类数和总金额。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
m, n = len(coins), amount
f = [[inf] * (n + 1) for _ in range(m + 1)]
f[0][0] = 0
for i, x in enumerate(coins, 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j]
if j >= x:
f[i][j] = min(f[i][j], f[i][j - x] + 1)
return -1 if f[m][n] >= inf else f[m][n]
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = amount
f = [0] + [inf] * n
for x in coins:
for j in range(x, n + 1):
f[j] = min(f[j], f[j - x] + 1)
return -1 if f[n] >= inf else f[n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity varies: DP approach is O(amount * n) where n is number of coins; BFS may also approach similar bounds. Space complexity is O(amount) for DP array or BFS visited set. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if candidate recognizes state transition DP pattern for minimal coin computation.
- question_mark
Looks for proper handling of edge cases like unreachable amounts or zero amount.
- question_mark
Observes whether BFS alternative is considered for level-based minimal coin counting.
常见陷阱
外企场景- error
Failing to initialize DP array correctly leading to invalid minimum computations.
- error
Ignoring unreachable sums, resulting in incorrect positive coin counts instead of -1.
- error
Overcounting coins by revisiting states without pruning already processed amounts.
进阶变体
外企场景- arrow_right_alt
Compute minimum coins when coins have limited quantity instead of infinite supply.
- arrow_right_alt
Return all possible combinations of coins that sum to the target amount.
- arrow_right_alt
Determine the number of ways to make up the amount rather than the minimal coins.