518. 零钱兑换 II（Coin Change 2）
频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯/美团
题目
不同面额硬币 coins（无限供应），凑目标金额 amount，求组合数（不关心顺序）。与 322 题的区别：322 求最少硬币数，本题求方案数。
示例：
输入: amount = 5, coins = [1,2,5]
输出: 4 （5, 2+2+1, 2+1+1+1, 1+1+1+1+1）
思路
完全背包计数（DP）：dp[i] 表示凑 i 元的组合数。
外层遍历硬币（保证每种组合只被计数一次，即「组合」而非「排列」），内层正向遍历金额：
dp[i] += dp[i - coin]
初始化 dp[0] = 1（凑 0 元只有一种方式：什么都不选）。
代码
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}复杂度
- 时间：O(amount × n) —— n 为硬币种类数
- 空间：O(amount)
边界条件
- amount = 0：返回 1（空组合）
- coins 为空且 amount > 0：dp 全为 0，返回 0
- 无法凑出 amount：dp[amount] 保持 0，返回 0
变式
- 322. 零钱兑换：求最少硬币数（最值问题），内外层循环顺序无关
- 377. 组合总和 Ⅳ：求排列数（顺序不同算不同），外金额内硬币，与本题恰好相反
- 39. 组合总和：求所有具体组合（回溯），本题只求计数
易错点
- 外层 coin、内层 amount：这是「组合不重复计数」的关键。如果外层 amount 内层 coin，会算出排列数（如 coins=[1,2]，amount=3 时会多算 2+1 和 1+2 两种顺序）。对比：322 求最值无所谓顺序，518 求组合数必须注意顺序
dp[0] = 1是 DP 基态（空集算一种组合），不是真实含义- 内层
for (int i = coin; i <= amount; i++)从 coin 开始遍历，因为 i < coin 时dp[i-coin]无意义
面试追问
- 为什么外层 coin 内层 amount 能避免重复计数？ 把硬币看作”选择顺序”——
coin=1先处理，coin=2后处理，所有使用 coin=2 的组合只能在 coin=1 全部处理完之后才出现，这样{1,2}和{2,1}只会被计数一次（只有 1 先、2 后的情况被计入）。本质上是在对硬币集合做「组合」而非「排列」 - 要求返回具体组合而不是计数怎么办？ 用回溯搜索（DFS），但 amount 很大时组合爆炸
- 硬币面额不是整数（如小数）怎么办？ DP 数组不能按金额索引，需要将金额乘以 10^k 转为整数再 DP，或者用哈希表做稀疏 DP
关联题
- 基础：322. 零钱兑换 —— 最值版，内外层循环不敏感
- 同套路：416. 分割等和子集 —— 0-1 背包（每个物品最多用一次）
- 进阶：39. 组合总和 —— 回溯求所有组合
- 知识点：完全背包的「组合」与「排列」计数区别见动态规划