LeetCode 题解工作台
零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1： 输入： amount = 5,…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示使用前 种硬币，凑出金额 的硬币组合数。初始时 $f[0][0] = 1$，其余位置的值均为 。 我们可以枚举使用的最后一枚硬币的数量 ，那么有式子一：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
解题思路
方法一：动态规划(完全背包)
我们定义 表示使用前 种硬币，凑出金额 的硬币组合数。初始时 ，其余位置的值均为 。
我们可以枚举使用的最后一枚硬币的数量 ，那么有式子一：
其中 表示第 种硬币的面值。
不妨令 ，那么有式子二：
将式子二代入式子一，得到：
最终的答案为 ，其中 和 分别表示硬币的种类数和总金额。
时间复杂度 ，空间复杂度 。其中 和 分别为硬币的种类数和总金额。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
m, n = len(coins), amount
f = [[0] * (n + 1) for _ in range(m + 1)]
f[0][0] = 1
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] += f[i][j - x]
return f[m][n]
我们注意到 只与 和 有关，因此我们可以将二维数组优化为一维数组，空间复杂度降为 。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = amount
f = [1] + [0] * n
for x in coins:
for j in range(x, n + 1):
f[j] += f[j - x]
return f[n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(amount * number of coins) since each coin updates all relevant dp indices. Space complexity is O(amount) using a single array for dynamic programming, capturing all state transitions efficiently. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to recognize the need for a state-based dynamic programming solution.
- question_mark
Watch for proper handling of unlimited coin usage without double-counting combinations.
- question_mark
Check if candidate can optimize space using a single dp array instead of 2D approaches.
常见陷阱
外企场景- error
Mistakenly counting permutations instead of combinations by updating the array incorrectly.
- error
Initializing dp array incorrectly or forgetting dp[0] = 1, causing all results to be zero.
- error
Iterating over amounts before coins, which can count duplicate combinations.
进阶变体
外企场景- arrow_right_alt
Change the target amount to a large value to test space-optimized dynamic programming.
- arrow_right_alt
Restrict coin usage to a maximum count per denomination to modify the state transition.
- arrow_right_alt
Compute minimum number of coins required instead of counting combinations for a variation.