贪心算法与动态规划：硬币找零问题的两种解法
引言在我们的日常生活中，经常遇到需要找零的情况。比如，在商场购物时，如果支付金额超过了商品的价格，那么收银员就需要给出一定数量的硬币或纸币作为找零。这个问题可以通过编程来解决，而解决的方法有两种常见的思路：贪心算法和动态规划。
一、贪心算法贪心算法是一种每一步都选择当前最优解的策略，期望通过一系列的局部最优解来达到全局最优解。对于硬币找零问题来说，贪心算法尝试每次从可用的硬币中选出面值最大的进行找零，直到找零完成或无法继续找零为止。
代码实现：function coinChangeGreedy(coins, amt) { // 假设coins是有序的 升序 let i = coins.length - 1; let count = 0; // 硬币数量 while (amt > 0) { // 还要找零 while (i >= 0 && coins[i] > amt) { i--; // 找到第一个小于等于amt的硬币 } if (i < 0) break; // 如果没有合适的硬币，则停止 amt -= coins[i]; count++; } return amt === 0 ? count : -1; }
在这个例子中，我们首先假设coins数组是按照升序排列的，然后尝试使用最大面额的硬币尽可能多地找零。这种方法虽然简单直观，但它并不总是能给出正确的答案，尤其是在某些特定情况下，如提供的硬币面额组合不适合贪心策略（例如[1, 20, 50]找60）。
二、动态规划动态规划（Dynamic Programming, DP）则是一种更加严谨的方法，它将问题分解成更小的问题，并保存这些子问题的答案，以避免重复计算。对于硬币找零问题，我们可以构建一个DP表，其中每个元素f[i]代表总额为i时所需的最少硬币数量。
代码实现：function coinChangeDp(coins, amount) { const f = Array(amount + 1).fill(Infinity); // 初始化dp数组 f[0] = 0; // 已知情况，找零为0时需要0个硬币 for (let i = 1; i <= amount; i++) { for (let j = 0; j < coins.length; j++) { if (i - coins[j] >= 0) { f[i] = Math.min(f[i], f[i - coins[j]] + 1); } } } return f[amount] === Infinity ? -1 : f[amount]; }
动态规划方法通过逐步构建解决方案，确保了最终结果的正确性。尽管它的实现可能比贪心算法复杂一些，但其优势在于它总能找到全局最优解，无论输入的硬币面额如何。
总结 贪心算法适合那些可以直接通过局部最优解推导出全局最优解的问题。它具有较低的时间复杂度，但不是所有问题都适用。 动态规划则更适合处理那些包含重叠子问题和最优子结构的问题。虽然通常时间复杂度较高，但它能够保证找到全局最优解。对于硬币找零问题而言，当硬币面额组合允许时，贪心算法可以快速得出答案；然而，为了确保答案的准确性，尤其是在面额组合不固定的情况下，动态规划提供了更为可靠的选择。
如果文章对你有帮助，请各位美女帅哥们点点赞 
