1. 问题背景与理解
零钱兑换问题是LeetCode上经典的动态规划题目（编号322），也是面试中高频出现的算法考题。题目要求：给定不同面额的硬币和一个总金额，计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，则返回-1。
举个例子：
- 输入：coins = [1, 2, 5], amount = 11
- 输出：3（因为5+5+1=11）
这个问题看似简单，但包含了几个关键点需要理解：
- 硬币可以无限次使用（完全背包问题）
- 需要找到"最少"硬币数的解（最优解问题）
- 需要考虑无解的情况（边界条件）
2. 暴力递归解法分析
2.1 递归思路构建
最直观的解法是暴力递归：对于给定的amount，尝试每一种硬币，然后递归求解剩余金额。
function coinChange(coins, amount) { function dp(n) { if (n === 0) return 0; if (n < 0) return -1; let res = Infinity; for (let coin of coins) { let subProblem = dp(n - coin); if (subProblem === -1) continue; res = Math.min(res, subProblem + 1); } return res !== Infinity ? res : -1; } return dp(amount); }2.2 递归解法的问题
这个解法虽然正确，但存在严重的性能问题：
- 时间复杂度：O(k^n)，其中k是硬币种类数，n是金额
- 存在大量重复计算，比如计算dp(10)时会重复计算dp(5)多次
在实际测试中，当amount=30，coins=[1,2,5]时，递归调用次数已经达到5373次，完全无法处理更大的输入。
3. 动态规划解法实现
3.1 自顶向下带备忘录的DP
通过添加备忘录来避免重复计算：
function coinChange(coins, amount) { const memo = new Map(); function dp(n) { if (memo.has(n)) return memo.get(n); if (n === 0) return 0; if (n < 0) return -1; let res = Infinity; for (let coin of coins) { let subProblem = dp(n - coin); if (subProblem === -1) continue; res = Math.min(res, subProblem + 1); } memo.set(n, res !== Infinity ? res : -1); return memo.get(n); } return dp(amount); }时间复杂度降为O(kn)，空间复杂度O(n)。
3.2 自底向上的DP解法
更常见的DP实现方式：
function coinChange(coins, amount) { // dp数组初始化为amount+1（相当于无穷大） let dp = new Array(amount + 1).fill(amount + 1); dp[0] = 0; for (let i = 1; i <= amount; i++) { for (let coin of coins) { if (i - coin >= 0) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; }这种实现有几个关键点：
- 初始化dp数组为amount+1（因为最多需要amount个1元硬币）
- 遍历顺序：外层循环金额，内层循环硬币
- 状态转移方程：dp[i] = min(dp[i], dp[i-coin]+1)
4. JavaScript实现细节与优化
4.1 边界条件处理
在实际编码中，有几个边界条件需要特别注意：
// 处理amount为0的情况 if (amount === 0) return 0; // 处理没有硬币或硬币面额无效的情况 if (!coins.length || coins.some(c => c <= 0)) { return -1; } // 可以先排序硬币，在某些情况下可以提前终止循环 coins.sort((a, b) => b - a);4.2 性能优化技巧
- 提前终止：当剩余金额小于当前硬币面额时，可以跳过
- 记忆化剪枝：在递归解法中，记录已经计算过的金额
- 空间优化：对于自底向上的DP，理论上可以优化空间复杂度，但因为需要保留所有中间结果，实际优化空间有限
// 优化后的DP实现 function coinChange(coins, amount) { coins.sort((a, b) => a - b); // 排序便于提前终止 let dp = new Array(amount + 1).fill(amount + 1); dp[0] = 0; for (let i = 1; i <= amount; i++) { for (let j = 0; j < coins.length; j++) { if (coins[j] > i) break; // 提前终止 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; }5. 常见错误与调试技巧
5.1 典型错误案例
初始化错误：
// 错误：初始化为0会导致Math.min失效 let dp = new Array(amount + 1).fill(0);循环顺序错误：
// 错误：内外层循环颠倒会导致错误结果 for (let coin of coins) { for (let i = 1; i <= amount; i++) { // ... } }边界条件遗漏：
// 错误：忘记处理amount为0的情况 if (amount < 0) return -1;
5.2 调试技巧
打印DP表：
console.log(dp); // 检查每个金额的最小硬币数是否正确小规模测试：
console.log(coinChange([1,2,5], 11)); // 应该输出3 console.log(coinChange([2], 3)); // 应该输出-1性能测试：
// 测试大规模输入 console.time('coinChange'); coinChange([1,2,5,10,20,50,100], 10000); console.timeEnd('coinChange');
6. 算法扩展与变种
6.1 计算组合数而非最小数量
如果题目改为"计算可以凑成总金额的组合数"，解法会有所不同：
function change(amount, coins) { let dp = new Array(amount + 1).fill(0); dp[0] = 1; for (let coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; }注意这里循环顺序的变化：外层循环硬币，内层循环金额，避免重复计算。
6.2 有限硬币数量的情况
如果每种硬币有数量限制（多重背包问题），解法需要再次调整：
function coinChangeLimited(coins, counts, amount) { let dp = new Array(amount + 1).fill(Infinity); dp[0] = 0; for (let i = 0; i < coins.length; i++) { for (let j = amount; j >= coins[i]; j--) { for (let k = 1; k <= counts[i] && k * coins[i] <= j; k++) { dp[j] = Math.min(dp[j], dp[j - k * coins[i]] + k); } } } return dp[amount] === Infinity ? -1 : dp[amount]; }7. 实际应用场景
零钱兑换算法在实际中有广泛的应用：
- 自动售货机找零系统：计算最少数量的硬币/纸币组合
- 金融系统的最小交易单位：将大额交易拆分为标准面额
- 资源分配优化：将总资源拆分为标准单元的最优组合
- 游戏开发：道具合成系统的最优路径计算
理解这个算法不仅能帮助通过技术面试，也能为解决实际工程问题提供思路。