1. 问题背景与理解
零钱兑换问题是动态规划领域的经典题目，在面试和算法竞赛中频繁出现。力扣第518题"零钱兑换II"要求我们计算给定硬币面额凑出指定金额的所有可能组合数。这与常见的"最少硬币数"问题不同，重点在于统计所有可能的组合方式。
举个例子，假设我们有硬币面额[1,2,5]，要凑出金额5。那么可能的组合方式有：
- 1+1+1+1+1
- 1+1+1+2
- 1+2+2
- 5
总共4种不同的组合方式。注意，这里的顺序不重要，1+2+2和2+1+2被视为同一种组合。
2. 动态规划解法思路
2.1 状态定义
我们使用一个一维数组dp，其中dp[i]表示凑出金额i的组合数。初始化时dp[0]=1，因为凑出金额0只有一种方式（不使用任何硬币）。
2.2 状态转移方程
对于每个硬币面额coin，我们遍历所有金额i从coin到目标金额amount，更新dp[i]的值：
dp[i] += dp[i - coin]这个方程的含义是：要凑出金额i，可以在凑出金额i-coin的基础上加上一个coin硬币。因此，凑出i的组合数等于所有i-coin的组合数之和。
2.3 遍历顺序
这里有一个关键点：外层循环应该是硬币面额，内层循环是金额。这样可以确保我们统计的是组合数而不是排列数。如果反过来，就会把1+2和2+1视为不同的情况。
3. Java实现代码
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]; }4. 代码解析与优化
4.1 时间复杂度分析
该算法的时间复杂度是O(n×amount)，其中n是硬币的种类数。空间复杂度是O(amount)，因为我们只使用了一个一维数组。
4.2 边界条件处理
需要注意几种特殊情况：
- 当amount为0时，应该返回1（不使用任何硬币）
- 当coins数组为空时，只有amount为0才能返回1，其他情况返回0
- 当没有任何组合能凑出amount时，返回0
4.3 空间优化
我们无法在时间上进一步优化，但可以观察状态转移方程发现，dp[i]只依赖于dp[i-coin]，因此可以使用一维数组来优化空间。
5. 测试用例与验证
为了确保代码的正确性，我们应该设计多种测试用例：
public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1：常规情况 int[] coins1 = {1, 2, 5}; System.out.println(solution.change(5, coins1)); // 预期输出：4 // 测试用例2：amount为0 System.out.println(solution.change(0, coins1)); // 预期输出：1 // 测试用例3：无解情况 int[] coins2 = {2}; System.out.println(solution.change(3, coins2)); // 预期输出：0 // 测试用例4：大额硬币 int[] coins3 = {10, 20, 50}; System.out.println(solution.change(50, coins3)); // 预期输出：4 }6. 常见错误与调试技巧
6.1 排列与组合混淆
最常见的错误是将组合数和排列数混淆。如果内外层循环写反了，就会得到排列数的结果。例如：
// 错误的写法：会计算排列数 for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] += dp[i - coin]; } } }6.2 初始化问题
忘记初始化dp[0]=1会导致所有结果都为0。这是因为任何金额都需要从dp[0]开始累加。
6.3 整数溢出
虽然题目中的amount通常不会太大，但在实际应用中，当amount很大时，dp数组的值可能会超出int的范围。可以考虑使用long类型。
7. 算法扩展与变种
7.1 最少硬币数问题
这是零钱兑换问题的另一个版本，要求找出凑出amount的最少硬币数。解法类似但状态转移方程不同：
public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; }7.2 打印所有组合
如果需要打印出所有可能的组合而不仅仅是计数，可以使用回溯法：
public List<List<Integer>> combinationSum(int[] coins, int amount) { List<List<Integer>> result = new ArrayList<>(); backtrack(coins, amount, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] coins, int remain, int start, List<Integer> temp, List<List<Integer>> result) { if (remain < 0) return; if (remain == 0) { result.add(new ArrayList<>(temp)); return; } for (int i = start; i < coins.length; i++) { temp.add(coins[i]); backtrack(coins, remain - coins[i], i, temp, result); temp.remove(temp.size() - 1); } }8. 实际应用场景
零钱兑换算法在实际中有广泛的应用：
- 金融领域的投资组合计算
- 库存管理中的货物组合
- 游戏开发中的道具合成系统
- 密码学中的某些加密算法
- 自动售货机的找零系统
理解这个问题的解法有助于我们解决许多类似的组合优化问题。动态规划的思想可以推广到资源分配、路径规划等多个领域。
