动态规划解决零钱兑换问题：LeetCode 322题解析

1. 问题背景与理解零钱兑换是Leetcode上经典的动态规划问题编号322。给定不同面额的硬币和一个总金额计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额则返回-1。这个问题在实际生活中非常常见比如自动售货机找零、银行柜台兑换零钱等场景。从算法角度来看它考察的是动态规划中的完全背包问题应用。2. 解题思路分析2.1 暴力递归法最直观的解法是尝试所有可能的硬币组合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); }这种方法时间复杂度为O(k^n)其中k是硬币种类数n是金额。存在大量重复计算效率极低。2.2 带备忘录的递归通过备忘录存储已计算结果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)。2.3 动态规划解法更高效的迭代解法function coinChange(coins, amount) { // dp数组初始化为amount1相当于无穷大 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]; }3. 代码实现细节3.1 初始化技巧dp数组初始化为amount1而不是Infinity因为最多只需要amount个1元硬币。这样最后可以直接比较dp[amount]和amount来判断是否有解。3.2 遍历顺序外层循环遍历所有金额内层循环遍历所有硬币。这样可以确保每个金额都尝试过所有可能的硬币组合。3.3 边界条件处理金额为0时需要返回0金额为负数时返回-1最终结果大于amount时返回-14. 复杂度分析时间复杂度O(kn)k是硬币种类数n是金额空间复杂度O(n)用于存储dp数组5. 测试用例设计好的测试用例应包含// 常规情况 console.log(coinChange([1, 2, 5], 11)); // 3 (551) console.log(coinChange([2], 3)); // -1 // 边界情况 console.log(coinChange([1], 0)); // 0 console.log(coinChange([1], 100)); // 100 // 性能测试 console.log(coinChange([186, 419, 83, 408], 6249)); // 206. 常见错误与调试6.1 初始化错误错误示例let dp new Array(amount 1).fill(0); // 错误初始化这会导致后续比较Math.min时始终得到0。6.2 遍历顺序错误错误示例for (let coin of coins) { for (let i 1; i amount; i) { // 错误顺序 // ... } }这样会导致某些硬币被重复使用次数不正确。6.3 边界条件遗漏忘记处理amount为0的情况if (amount 0) return 0; // 必须添加7. 算法优化思路7.1 提前排序将硬币按面额从大到小排序可以尽早找到较大面额的解coins.sort((a, b) b - a);7.2 剪枝优化在递归解法中如果当前硬币数已经超过已知最小解可以提前终止if (count minCount) return; // 剪枝8. 实际应用扩展这个问题可以扩展到求所有可能的组合数Leetcode 518硬币面额有限制的情况输出具体的硬币组合9. JavaScript性能注意事项使用Array代替Map可以获得更好的性能避免在循环中创建新数组对于超大金额可以考虑使用贪心算法先估算下限10. 总结与个人心得零钱兑换问题是理解动态规划的绝佳案例。在实际编码中我发现dp数组的初始化值很关键需要大于任何可能的有效解遍历顺序会影响是否能重复使用物品完全背包与01背包的区别JavaScript中数组操作比Map更快适合这种数值型dp问题建议初学者可以先用递归备忘录的方式理解问题再转化为迭代解法。多设计几个测试用例验证边界条件特别是amount为0和无法兑换的情况。