1. 项目概述从“找零钱”到算法思维的跃迁“找零钱”这个问题几乎是我们每个人在日常生活中都会遇到的场景。你去便利店买一瓶3块钱的饮料递给收银员10块钱他需要找给你7块钱。这个看似简单的过程背后其实蕴含着一个经典的算法问题如何用最少数量的硬币或纸币凑出指定的金额在LeetCode上这个问题通常以“Coin Change”或“零钱兑换”的形式出现是算法面试中的“常客”也是区分候选人是否真正理解贪心算法与动态规划核心差异的绝佳试金石。我之所以想深入聊聊这个问题是因为我发现很多朋友在初次接触时很容易陷入一个思维定式这不就是每次都选最大面额的硬币不就行了吗比如在中国要找7块钱最优解自然是1张5元加1张2元。这个直觉在大多数日常场景下是成立的因为它恰好符合我们人民币的硬币/纸币面额设置1, 2, 5, 10, 20, 50, 100。这种“每次都选当前能用的最大面额”的策略就是贪心算法的核心思想。它在特定条件下专业术语叫“具有贪心选择性质”又快又好。但问题恰恰就出在这个“特定条件”上。如果面额体系变了呢比如面额是[1, 3, 4]要凑出6块钱。贪心策略会怎么选先拿4剩下2只能用两个1总共用了3枚硬币411。然而最优解其实是两个3只需要2枚硬币。看贪心策略在这里就“失灵”了它得到了一个次优解。这个反例就像一盆冷水瞬间浇醒了我们原来直觉并不总是可靠我们需要一个更强大、能保证在任何情况下都找到最优解的方法。这就是动态规划登场的时刻。所以这个项目标题“找零钱问题贪心||动规”的精髓就在于这个“||”或。它不是一个简单的并列而是一个深刻的递进和对比。我们将从一个看似简单直观的贪心解法入手剖析其原理和局限性然后自然而然地引出动态规划这个“万能钥匙”详细拆解其状态定义、转移方程和实现细节。通过这个问题我们真正要掌握的不是两个孤立的算法而是一套完整的算法设计思维如何分析问题性质如何根据问题特性选择或设计算法以及当一种方法失效时如何系统性地寻找更通用的解决方案。无论你是正在刷题准备面试的求职者还是希望夯实算法基础的开发者吃透这个问题都将对你理解更复杂的优化问题大有裨益。1.1 核心需求与场景解析找零钱问题的核心需求非常明确给定一个整数金额amount和一组不同面额的硬币coins假设每种硬币数量无限计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成该金额则返回-1。这个抽象的问题模型其应用场景远不止于真实的货币找零资源最优分配在云计算或分布式系统中如何用几种规格固定的虚拟机对应硬币面额来满足一个计算任务的总资源需求对应总金额使得使用的虚拟机实例总数最少从而降低成本。商品组合优化在电商促销中有多种面额的优惠券如满100减20、满200减50顾客想购买一件商品如何组合使用这些优惠券使得实付金额最低可以转化为用优惠券面额凑“减免金额”求最少使用张数。路径规划简化在某些简化模型中从一个点到另一个点有若干种固定长度的“跳跃”方式求到达目标的最少步数。算法竞赛与面试这是动态规划入门最经典的例题之一考察对状态、子问题、最优子结构等概念的理解。从输入输出看问题接口通常如下def coinChange(coins, amount): # 输入 coins - List[int], 硬币面额列表 # amount - int, 目标总金额 # 输出 int, 最少硬币数无法凑出则返回-1例如coins [1, 2, 5],amount 11答案应该是3(551)。问题的难点在于搜索空间巨大硬币数量无限组合方式是指数级的暴力枚举不可行。最优子结构凑出金额i的最优解可以通过凑出金额i - coin的最优解加上一枚coin面额的硬币来得到。这是动态规划可行的基础。重叠子问题在递归求解过程中例如计算amount11会反复计算amount6,amount9等子问题直接递归会有大量重复计算。因此我们的任务就是设计算法高效地利用这些性质找到全局最优解。2. 贪心算法直觉的陷阱与适用的天堂让我们先从最符合直觉的贪心算法开始。贪心算法的思想是在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的。对于找零钱这个“当前最优”就是“选择不超过剩余金额的最大面额硬币”。2.1 贪心算法的实现与模拟假设硬币面额数组coins已经按从大到小排序。算法步骤清晰直接初始化剩余金额remain amount使用硬币数量count 0。从大到小遍历排序后的coins当remain coin时计算最多可以使用几枚该面额硬币num remain // coin。count加上num。remain减去num * coin。遍历结束后如果remain 0返回count否则返回-1表示无法凑出。用Python实现如下def coinChange_greedy(coins, amount): # 先将硬币面额从大到小排序 coins.sort(reverseTrue) count 0 remain amount for coin in coins: if remain 0: break if coin remain: num remain // coin # 当前面额最多能用几枚 count num remain - num * coin return count if remain 0 else -1我们来模拟一下前面提到的两个例子例子A人民币体系coins [5, 2, 1],amount 7。遍历coin5:remain7 5,num1,count1,remain2遍历coin2:remain2 2,num1,count2,remain0结束返回count2。正确。例子B反例体系coins [4, 3, 1],amount 6。遍历coin4:remain6 4,num1,count1,remain2遍历coin3:remain2 3跳过。遍历coin1:remain2 1,num2,count3,remain0结束返回count3。但我们知道最优解是233。注意在面试或实践中如果直接写出这个贪心算法并声称它适用于所有情况很可能是一个严重的失误。你必须能够主动指出它的局限性。2.2 贪心为何会失败深入理解“贪心选择性质”贪心算法要能获得全局最优解问题必须满足“贪心选择性质”即每一步的局部最优选择能导致最终的全局最优解。对于硬币找零问题这个性质成立与否完全取决于硬币面额的设定。为什么 [1, 2, 5] 可以而 [1, 3, 4] 不行关键在于在 [1, 2, 5] 这个面额体系中任何面额之间都存在整数倍关系或者可以相互组合成更大面额且大面额不是小面额的简单倍数时其组合依然对贪心友好。更专业的说法是许多国家的货币系统如人民币、美元是“规范”或“正则”的这种系统被设计成贪心算法有效。而对于 [1, 3, 4]当amount6时贪心首选4导致剩下2只能用两个1路径是 4 - 1 - 1。但最优路径是 3 - 3。贪心算法在第一步选择了“看起来最大”的4但这个选择堵死了后续达到更优解两个3的可能性。也就是说局部最优选4没有导向全局最优。一个更极端的反例coins [1, 5, 11],amount 15。贪心选11 - 剩下4 - 四个1共5枚硬币。最优三个5共3枚硬币。这里贪心算法甚至没有使用面额为5的硬币因为它被更大的11“带偏”了。2.3 贪心算法的适用场景与实战心得尽管贪心算法不能解决通用的找零钱问题但它在特定场景下依然是利器已知面额体系满足贪心性质如果你的问题场景明确是人民币、美元等标准货币贪心算法是首选因为它时间复杂度是 O(n log n)排序或 O(n)如果已排序远优于动态规划。作为动态规划的优化或启发在动态规划求解过程中有时可以用贪心思想进行剪枝。例如在搜索或DP过程中如果当前硬币数已经超过了贪心解得到的硬币数那么这条路径可以提前终止因为它不可能更优。解决变种问题LeetCode上有一道题“柠檬水找零”LeetCode 860它只有5、10、20三种面额且顾客支付顺序固定。这个问题用纯粹的贪心模拟收银过程就能完美解决因为面额设置和交易规则使得贪心选择总是正确的。实操心得永远先问面额遇到类似问题第一反应不是写代码而是确认硬币面额是否固定以及是否满足贪心性质。可以快速在脑中用几个小金额测试一下。排序是必要步骤贪心实现前务必对coins进行降序排序。这是一个常见的失分点。边界检查如果最小的硬币面额都大于amount且amount不为0那么除了amount0返回0的情况外其他情况都无法凑出。可以在循环前加一个快速判断if amount 0 and min(coins) amount: return -1。贪心算法像一把锋利但用途特定的手术刀在它的适用范围内无比高效但一旦用错场景就会得出错误答案。当我们发现贪心算法可能失效或者问题描述没有保证面额体系的性质时就必须请出更强大的工具——动态规划。3. 动态规划系统性的最优解搜寻引擎当贪心算法因为面额问题“翻车”时动态规划Dynamic Programming, DP提供了系统性的解决方案。它的核心思想是“记住过去避免重复计算”通过将大问题分解为相互重叠的子问题并存储子问题的解记忆化来高效求解原问题。对于找零钱问题DP是标准的、正确的解法。3.1 动态规划的思路拆解自顶向下与自底向上理解DP解找零钱问题有两个经典的角度自顶向下带备忘录的递归和自底向上的迭代。1. 自顶向下记忆化搜索这更符合人类的自然思维要凑amount我最后一枚硬币可以是coins中的任何一个。如果我选了coin那么问题就变成了凑amount - coin这个子问题。如果我知道了凑amount - coin的最少硬币数sub_res那么凑amount的最少硬币数就是sub_res 1。我需要遍历所有可能的coin选择结果最小的那个。 为了避免重复计算子问题我们用一个数组或字典memo来记录已经计算过的金额所需的最少硬币数。2. 自底向上迭代填表这是更常见的DP实现方式也更容易优化。我们定义一个DP数组dp其中dp[i]表示凑出总金额i所需的最少硬币数。我们的目标是求dp[amount]。初始状态dp[0] 0凑出0元需要0枚硬币。状态转移方程对于每个金额i从1到amount我们遍历每个硬币coin如果coin i说明这枚硬币可以用那么一种可能的凑法就是先凑出i - coin然后再加一枚coin。所以dp[i]应该是所有dp[i - coin] 1中的最小值。用公式表示dp[i] min(dp[i], dp[i - coin] 1)forcoin in coinsifcoin i。最终答案dp[amount]如果它没有被更新还是初始值说明无法凑出返回-1。自底向上的方法逻辑清晰且更容易进行空间优化滚动数组是面试中的首选写法。3.2 标准动态规划实现与逐行解析下面给出自底向上DP的标准实现并附上详细注释。def coinChange(coins, amount): 使用动态规划解决零钱兑换问题 :type coins: List[int] :type amount: int :rtype: int # 初始化dp数组长度为 amount1因为我们要表示从0到amount的所有金额 # 初始值设置为一个很大的数这里用 amount1 或 float(inf) 都可以。 # amount1 是一个有效的上界因为最多的情况就是用1元硬币凑需要amount枚。 dp [amount 1] * (amount 1) dp[0] 0 # 边界条件凑0元需要0个硬币 # 外层循环遍历所有金额状态从1到amount for i in range(1, amount 1): # 内层循环遍历所有硬币选择 for coin in coins: # 只有当当前硬币面额小于等于目标金额i时才有可能使用这枚硬币 if coin i: # 状态转移dp[i] 可以通过 dp[i-coin] 1 转移过来 # 我们取所有可能转移中的最小值 dp[i] min(dp[i], dp[i - coin] 1) # 如果 dp[amount] 没有被更新仍然等于初始值 amount1说明无法凑出 # 否则返回 dp[amount] return dp[amount] if dp[amount] ! amount 1 else -1关键点解析DP数组初始化dp [amount 1] * (amount 1)。为什么是amount 1因为最坏情况是用面额为1的硬币凑需要amount枚。将初始值设为amount 1一个比可能最大值还大的数可以方便后续用min()函数更新并且最后可以通过判断是否等于这个“无效值”来确定能否凑出。使用float(inf)也是可以的。边界条件dp[0] 0这是整个DP的基石。它表示凑出0元不需要任何硬币。没有这个正确的起点后面的所有状态都无法正确转移。双重循环的顺序外层循环遍历金额i内层循环遍历硬币coin。这个顺序是固定的它确保了在计算dp[i]时所有更小的子问题dp[i-coin]都已经被计算出来了因为i-coin i。这是自底向上DP的典型特征。状态转移方程dp[i] min(dp[i], dp[i - coin] 1)这是核心逻辑。对于每个i我们都尝试所有可能的“最后一枚硬币”coin。dp[i - coin]是凑出剩余金额的最优解加上这枚硬币就是当前选择下的解。我们不断用更小的值更新dp[i]最终得到最小值。返回值判断如果最终dp[amount]还是初始的amount 1说明没有任何一种硬币组合能凑出amount返回-1。时间复杂度O(S * n)其中 S 是金额amountn 是硬币种类数。我们需要计算 S 个状态每个状态需要遍历 n 种硬币选择。空间复杂度O(S)即 DP 数组的大小。3.3 从DP表理解算法运行过程让我们以coins [1, 2, 5],amount 11为例手动推演一下DP表这能极大地加深理解。初始化dp [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]dp[0] 0。i 1:coin1:11,dp[1] min(12, dp[0]11) 1coin2,5跳过。dp[1] 1(11)i 2:coin1:dp[2] min(12, dp[1]12) 2coin2:dp[2] min(2, dp[0]11) 1coin5跳过。dp[2] 1(22)i 3:coin1:dp[3] min(12, dp[2]12) 2coin2:dp[3] min(2, dp[1]12) 2coin5跳过。dp[3] 2(321)i 4:coin1:dp[4] min(12, dp[3]13) 3coin2:dp[4] min(3, dp[2]12) 2coin5跳过。dp[4] 2(422)i 5:coin1:dp[5] min(12, dp[4]13) 3coin2:dp[5] min(3, dp[3]13) 3coin5:dp[5] min(3, dp[0]11) 1dp[5] 1(55)i 6:coin1:dp[6] min(12, dp[5]12) 2coin2:dp[6] min(2, dp[4]13) 2coin5:dp[6] min(2, dp[1]12) 2dp[6] 2(651)... 以此类推最终计算到i11。i 11:coin1:dp[11] min(12, dp[10]1?)假设dp[10]2则值为3。coin2:dp[11] min(3, dp[9]1?)假设dp[9]2则值为3。coin5:dp[11] min(3, dp[6]13) 3dp[11] 3(11551)通过这个过程我们可以看到每个dp[i]是如何由更小的dp[i-coin]推导出来的完美体现了最优子结构。4. 动态规划的优化与变种探讨掌握了标准DP解法后我们可以进一步探讨一些优化技巧和相关的变种问题这能帮助你在面试中脱颖而出。4.1 空间优化滚动数组的思想在上述标准DP中我们使用了一个长度为amount1的数组。仔细观察状态转移方程dp[i] min(dp[i], dp[i - coin] 1)在计算dp[i]时它只依赖于下标小于i的那些状态。这是否意味着我们可以优化空间呢严格来说对于这个特定的状态转移方程dp[i]依赖于多个dp[i-coin]而这些i-coin的值相差可能很大无法用一个固定大小的滚动窗口来覆盖因此不能像经典的0-1背包问题那样优化到一维数组且内层循环逆序。我们当前的一维dp数组已经是比较节省空间的形式了。但是有一种理解角度我们可以把dp数组的更新看作是在原本全为无穷大的数组中用每个硬币去“松弛”各个金额的状态。这个过程和图的广度优先搜索BFS或者最短路径算法中的松弛操作很像。不过从编码实现上看保持当前的一维数组形式就是最清晰和高效的。4.2 变种问题凑出金额的所有组合数LeetCode 518这是一个非常经典的变种给定不同面额的硬币和一个总金额写出函数来计算可以凑成总金额的硬币组合数。注意这里是组合数顺序不同视为同一种组合。例如coins [1, 2, 5],amount 5组合有5 221 2111 11111。共4种。解法思路的转变 在求“最少硬币数”时我们的状态转移是dp[i] min(dp[i], dp[i-coin]1)是求最小值。 在求“组合数”时我们的状态定义要变dp[i]表示凑出金额i的组合数。 状态转移方程变为dp[i] dp[i - coin]。 这里有一个至关重要的循环顺序问题如果外层循环是金额i内层循环是硬币coin即for i in range(1, amount1): for coin in coins: if coin i: dp[i] dp[i - coin]这样计算出来的是排列数因为对于amount3, coins[1,2]它会认为 (1,2) 和 (2,1) 是两种不同的方法。为了求组合数我们需要外层循环遍历硬币内层循环遍历金额。这保证了在考虑任何金额时硬币的引入顺序是固定的避免了同一组硬币因顺序不同而被重复计算。dp [0] * (amount 1) dp[0] 1 # 凑出0元有一种组合什么都不选 for coin in coins: # 外层遍历硬币 for i in range(coin, amount 1): # 内层遍历金额 dp[i] dp[i - coin] return dp[amount]这样在计算dp[i]时我们只使用“当前及之前”的硬币不会使用“之后”的硬币从而保证了组合的唯一性。这个“循环顺序”的细节是面试中的高频考点务必理解其背后的原因它控制了状态转移时物品硬币被考虑的维度从而决定了结果是组合还是排列。4.3 边界条件与初始化陷阱动态规划的边界条件处理不当是导致错误的主要原因之一。dp[0]的初始化在最少硬币数问题中dp[0]0是显然的。在组合数问题中dp[0]1代表“凑出0元有一种方法即什么都不选”这是组合数学中的空集概念也是正确的递推基础。无法凑出的情况在最少硬币数问题中我们用amount1或inf初始化最后判断是否等于该值。切勿初始化为-1因为状态转移方程中有min操作-1会被当成更小的值导致逻辑错误。金额为0的情况如果amount 0根据题目定义需要0枚硬币可以凑出所以应该返回0。你的DP代码应该能正确处理这种情况我们的实现中初始化dp[0]0循环从1开始对于amount0直接返回dp[0]即0。硬币数组为空如果coins为空对于任何amount 0都应该返回-1。代码中内层循环遍历coins如果coins为空则dp[i]永远不会被更新最终会返回-1符合预期。5. 实战对比与问题排查实录现在让我们将贪心和动规放在一起对比并总结实际编码和调试中会遇到的问题。5.1 贪心与动规的对比总结特性贪心算法动态规划核心思想每一步做出当前最优选择将问题分解为重叠子问题存储并复用子问题解时间复杂度O(n log n) 或 O(n)O(S * n)空间复杂度O(1) 或 O(n)排序O(S)解的正确性仅在面额满足贪心选择性质时正确总是能得到全局最优解适用场景标准货币体系、特定变种问题通用找零问题、组合计数问题等编码难度简单直观中等需设计状态和转移方程思维难度低但需判断适用性高需要识别最优子结构和重叠子问题如何选择如果问题明确说明硬币面额是标准货币如1,2,5,10...或者像“柠檬水找零”那样有特殊规则保证贪心有效优先用贪心又快又简单。如果问题没有明确说明或者面额是任意给定的一律使用动态规划。这是最稳妥、不会出错的方法。在面试中即使你直觉是贪心也最好先提一下贪心的思路和它的局限性然后说“为了得到通用解我们采用动态规划”这会显得你思考全面。5.2 常见错误与调试技巧在实现动态规划解时以下几个错误非常常见DP数组初始化错误错误dp [0] * (amount 1)然后将dp[0]0其他为0。这样在求min时0永远是最小值结果永远为0。正确初始化为一个很大的数如amount 1或float(inf)。状态转移方程遗漏dp[i]错误dp[i] dp[i - coin] 1。这没有考虑所有coin的选择会直接被最后一次计算覆盖。正确dp[i] min(dp[i], dp[i - coin] 1)。必须用min来保留所有可能中的最小值。内层循环条件忽略错误直接计算dp[i - coin] 1没有判断coin i。当coin i时i-coin为负数会导致数组越界或访问无效内存。正确务必加上if coin i:的判断。返回值逻辑错误错误直接return dp[amount]。如果无法凑出dp[amount]可能还是初始的大数值需要特殊处理。正确return dp[amount] if dp[amount] ! amount 1 else -1。调试技巧打印DP表对于小规模的amount比如10以内在循环中打印出dp数组的中间状态是验证逻辑最直观的方法。观察每个dp[i]是否按预期更新。使用简单测试用例先用coins[1], amount0/1/2测试边界。再用coins[2], amount3测试无法凑出的情况。最后用coins[1,2,5], amount11测试正常功能。对比贪心结果对于标准面额可以用贪心算法的结果来验证DP结果的正确性。理解“为什么是min”在脑子里过一遍状态转移确认dp[i]确实应该取所有可能来源的最小值。5.3 复杂度分析与优化思考对于动态规划解法时间复杂度 O(S * n) 在amount很大例如10^4且硬币种类多时可能会成为瓶颈。但在LeetCode的典型约束下amount 10^4,n 12这个复杂度是完全可接受的。如果遇到极端情况可以考虑以下优化方向提前排序与剪枝将coins排序在内层循环中一旦coin i就可以break因为后面的硬币更大。coins.sort() # 升序排序 for i in range(1, amount1): for coin in coins: if coin i: # 因为已排序后面的coin都大于i直接跳出内循环 break dp[i] min(dp[i], dp[i-coin] 1)使用BFS思想将问题转化为求从0到amount的最短路径每个硬币面额代表一步的“长度”。用BFS可以保证第一次到达amount时所用的步数就是最少硬币数。这种方法在最坏情况下复杂度类似但实际平均可能更快尤其当硬币面额较大时。数学方法对于特定面额组合可能存在数学公式或规律但这属于竞赛级优化面试中几乎不需要。找零钱问题就像算法世界里的一个经典模型它清晰地展示了从直观贪心到系统动态规划的思维演进。理解它不仅是为了解决一道题更是为了掌握一种分析复杂问题、设计可靠算法的方法论。下次当你再遇到“最少”、“最短”、“最优”这类字眼时不妨先想想这个问题有没有最优子结构能不能用动态规划来定义状态和转移这套思维模式才是刷题带给我们的真正财富。