华为 OD 训练营 · 题解精讲
LC518. 零钱兑换II
LC518. 零钱兑换II
题目描述
给你一个整数数组 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 <= 300 1 <= coins[i] <= 5000 coins 中的所有值 互不相同 0 <= amount <= 5000
题目解析
解题思路
本题是完全背包求组合数的经典问题。硬币无限，顺序不同的相同组合视为同一种，因此必须按硬币顺序遍历，避免重复计数。
用动态规划，定义 dp[i][j] 表示使用前 i 种硬币凑出金额 j 的组合数。状态转移时，对第 i 种硬币有两种选择：不选（继承 dp[i-1][j]）或选一个（剩余金额 j - coins[i-1] 仍可用第 i 种硬币，即 dp[i][j-coins[i-1]]）。这正是完全背包的转移方程。
一维优化：将 dp 压缩为 dp[j]，外层循环硬币，内层正序遍历金额，保证每种硬币可多次使用。
关键步骤
1. 初始化：dp[0] = 1，表示凑 0 元只有 1 种方式（不选任何硬币）。 2. 外层循环：遍历每种硬币 coin。 3. 内层循环：从 coin 到 amount 正序更新：
dp[j] += dp[j - coin]正序确保当前硬币可以被多次选取（完全背包特性）。 4. 最终 dp[amount] 即为答案。
示意图（以 coins=[1,2], amount=3 为例）：
初始: dp = [1, 0, 0, 0]
coin=1: dp[1]=dp[1]+dp[0]=1 → [1,1,0,0]
dp[2]=dp[2]+dp[1]=1 → [1,1,1,0]
dp[3]=dp[3]+dp[2]=1 → [1,1,1,1]
coin=2: dp[2]=dp[2]+dp[0]=2 → [1,1,2,1]
dp[3]=dp[3]+dp[1]=2 → [1,1,2,2]
结果: dp[3]=2 (组合: 1+1+1, 1+2)复杂度分析
- 时间复杂度：O(n × amount)，n 为硬币种类数，amount 为总金额。两层循环，每层最多 amount 次。
- 空间复杂度：O(amount)，一维数组长度 amount+1。
参考代码
二维DP
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
dp = [[0]*(amount+1) for _ in range(n+1)]
# 初始化
dp[0][0] = 1
# 完全背包
# 第一层循环：遍历硬币
for i in range(1, n+1):
# 第二层循环：遍历背包
for j in range(amount+1):
# 容量有限，无法选择第i个硬币
if j < coins[i-1]:
dp[i][j] = dp[i-1][j]
# 可选择第i个硬币
else:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
return dp[n][amount]
一维DP
class Solution:
def change(self, amount: int, coins: list[int]) -> int:
# 经典的完全背包问题
# 一维数组：状态定义 dp[j] 表示组合得到金额 j 的方案数
dp = [0] * (amount + 1)
# 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
dp[0] = 1
# 遍历每种硬币
for coin in coins:
# 遍历背包容量，从当前硬币值到总金额
for j in range(coin, amount + 1):
# 如果选择当前硬币coin，组合方案数增加dp[j - coin]
dp[j] += dp[j - coin]
# 返回最终能凑成金额 amount 的组合数
return dp[amount]