跳至主要內容

硬币找零问题

孔繁强大约 15 分钟教学文档算法设计与分析动态规划完全背包最小值优化Python

硬币找零问题

中等 完全背包优化 Python

“买包子”已经能判断一个数量能不能凑出。如果还要求“用的笼数最少”,状态需要怎样改变? 把蒸笼容量换成硬币面额,把布尔值换成最少枚数,就得到本题的思路。

本节学习目标

  • 会迁移: 从买包子的可达性状态,转化为硬币找零的最小值状态。
  • 会推导: 根据最后一枚硬币定义子问题,说明初始化、转移与不可达状态。
  • 会核对: 跟踪金额递增的计算过程,区分可行性、最少枚数和组合数量。

前置知识:买包子中的无限使用与可达性;学习后可对照零钱兑换理解组合计数。

题目描述

给定正整数列表 coins 表示可用的硬币面额,以及非负整数 amount 表示目标金额。每种面额的硬币数量无限,求恰好凑出目标金额所需的最少硬币枚数。

如果无法恰好凑出,返回−1;金额为0时,返回0。本题只返回最少枚数,不要求程序恢复具体硬币组合,也不统计组合数量。

交互动画另提供“恢复一种最优硬币组合”的教学扩展:记录各可达金额的最后一枚硬币,再从目标金额逐次扣减该面额,直到0。动画将面额去重并递增排列,候选相等时保留较小的最后一枚面额;Python主实现仍只返回最少枚数。

参数、范围与规则

项目约定
面额列表coins,长度n满足 1≤n≤121\leq n\leq12
单个面额正整数,1≤coins[i]≤231−11\leq coins[i]\leq2^{31}-1
目标金额整数,0≤amount≤1040\leq amount\leq10^4
使用次数每种面额可使用0枚、1枚或更多枚
凑出要求金额必须恰好相等,不能超过目标
输入顺序面额不要求有序;主实现不修改输入列表
下标规则Python列表从0开始,第i个列表位置的面额为coins[i]

输入保证满足上述条件。重复面额不改变最少枚数,只会产生重复的候选比较;零面额、负面额与小数不属于有效输入。

贯穿示例

输入: coins = [1, 2, 5], amount = 11
输出: 3
说明: 11 = 5 + 5 + 1,共3枚。
输入输出原因
coins=[2], amount=3−1任意多枚2元都不能凑出3元
coins=[1], amount=00不使用任何硬币即可
coins=[1,3,4], amount=62使用3元、3元,比4元、1元、1元更少

最后一个例子也说明:每次优先拿最大面额的贪心策略,对任意面额集合不一定得到最优解。

题目分析

从买包子的“能否凑出”向前走一步

买包子中,每种蒸笼容量无限使用,先判断某个数量是否能够凑出,再统计指定范围或题目要求范围内的不可达数量。本题则给定一个目标,进一步比较各种凑法的使用次数。

对照项目买包子的可达性子问题硬币找零
每种规格一笼包子数a一枚硬币面额c
状态can[s]:能否凑出sdp[s]:凑出s最少需要几枚
零状态can[0] = Truedp[0] = 0
暂不可达False无穷大
合并来源有一个来源可达就可达比较所有可达来源的使用枚数,取最小值

买包子可以从“s−a能够凑出”推出“再加一笼后s能够凑出”。本题保留更多信息:若s−c最少需要k枚,再加一枚c,就得到凑出s的一种k+1枚方案。

因此,最小值状态也包含可达性信息:dp[s] 有限就表示可达;只有布尔值时,则无法判断两种可行方案谁用的硬币更少。

定义状态与边界

定义 dp[s]:使用给定的全部面额,恰好凑出金额s所需的最少硬币枚数。 暂时无法凑出时,记为无穷大。

dp[0]=0,dp[s]=+∞(1≤s≤amount). dp[0]=0,\qquad dp[s]=+\infty\quad(1\leq s\leq amount).

这里的0表示需要0枚硬币,不是有0种方案。金额0在组合计数问题中有一种空组合,但在本题中它的最少使用枚数为0。

也可以用数量向量表示本题:设第i种面额为 cic_i,其使用枚数为非负整数 xix_i,其中 0≤i<n0\leq i<n,目标为:

min⁡∑i=0n−1xi,满足∑i=0n−1cixi=amount. \min\sum_{i=0}^{n-1}x_i, \qquad\text{满足}\quad \sum_{i=0}^{n-1}c_ix_i=amount.

根据最后一枚硬币推导转移

对于正金额s,假设最后加入的一枚硬币面额为c:

  1. 必须有c≤s,否则剩余金额为负数。
  2. 去掉这枚硬币,剩下的金额为s−c。
  3. 若s−c可达,则当前候选需要 dp[s - c] + 1 枚。
  4. 比较所有合法面额的候选,取最少枚数。

得到:

dp[s]=min⁡c∈coinsc≤s(dp[s−c]+1). dp[s]=\min_{\substack{c\in coins\\c\leq s}} \bigl(dp[s-c]+1\bigr).

无合法面额或所有来源均不可达时,状态仍为无穷大。由于所有面额为正数,s−c严格小于s,按金额从小到大计算,就能保证依赖状态已求出。

为什么只保存最少枚数即可

任意一个凑出s的方案,都能去掉其中一枚面额c,得到凑出s−c的方案。如果这部分不是最优的,就可以换成凑出相同金额、使用更少枚数的方案,再补回一枚c,总金额不变,枚数不会增加。

每个可达来源补上一枚c,确实构成当前金额的一种合法方案;而比较全部面额,又不会漏掉最优方案的最后一枚硬币。因此该转移恰好得到最少枚数。

同一组硬币可能以不同顺序被比较到,但取最小值不会累计重复次数。这一点与组合计数中的加法不同。

不可达标记与返回值

Python主实现使用 unreachable = amount + 1 代替无穷大。

因为面额至少为1,凑出金额s的任何方案至多使用s枚;因此任何有效答案都不超过amount。amount+1不可能与有效最优值混淆。

代码只从可达状态转移。最终若 dp[amount] 仍为不可达标记,返回−1,否则返回记录的最少枚数。

无限使用、循环顺序与组合计数

主实现按金额递增,再比较所有面额。每次都可以从较小金额的最优结果继续加硬币,不记录“某种面额已经使用过”,因此允许重复使用。

也可以像买包子的代码一样,先遍历面额,再把金额从该面额递增到目标,使用相同的最小值更新。这对应逐步增加可用面额的完全背包写法,同样正确;若采用这种写法,金额倒序则会变成每个面额条目至多使用一次。

但不能把这些结论直接套到零钱兑换的组合计数:那里转移使用加法,金额在外、面额在内会重复统计不同顺序。本题使用 min,重复比较同一个组合不会改变最小值。

实现代码

Python 按金额递增实现

coin_change(coins, amount) 返回最少硬币枚数。以下程序可直接复制运行,输入满足题目约定,无需额外安装依赖。

def coin_change(coins, amount):
    """每种面额无限使用,返回最少枚数;无法恰好凑出时返回-1。"""
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)
    dp[0] = 0

    for s in range(1, amount + 1):
        for coin in coins:
            if coin <= s and dp[s - coin] != unreachable:
                dp[s] = min(dp[s], dp[s - coin] + 1)

    return -1 if dp[amount] == unreachable else dp[amount]


if __name__ == "__main__":
    cases = [
        ([1, 2, 5], 11),
        ([2], 3),
        ([1], 0),
        ([1, 3, 4], 6),
        ([3, 4], 6),
        ([3, 4], 5),
    ]
    for coins, amount in cases:
        print(f"coins={coins}, amount={amount} -> {coin_change(coins, amount)}")

运行输出:

coins=[1, 2, 5], amount=11 -> 3
coins=[2], amount=3 -> -1
coins=[1], amount=0 -> 0
coins=[1, 3, 4], amount=6 -> 2
coins=[3, 4], amount=6 -> 2
coins=[3, 4], amount=5 -> -1
关键代码对应含义
dp[0] = 0零金额需要0枚硬币
range(1, amount + 1)逐个计算正金额,包含目标amount
coin <= s保证剩余金额非负,避免误用Python负下标
dp[s - coin] != unreachable只从确实可达的金额扩展
dp[s - coin] + 1在最优子方案上增加一枚当前硬币
min(...)比较候选的枚数,而非累计方案数量

面额大于目标时,只会在比较中被跳过。金额为0时,循环不执行,直接返回 dp[0],即0。

算法执行过程

交互动画

下方演示与Python主实现一样,按金额递增计算,逐个比较可用面额。默认输入为 coins = [1,2,5]、amount = 11,最终最少枚数为3。

  • 每个格子的下标是金额,值是最少枚数;黄色边框表示正在计算,绿色标出已得到有限值的状态。符号∞表示当前不可达标记 amount + 1,只有目标状态最终不可达时才返回−1。
  • 公式面板依次展开来源下标、旧状态值、候选枚数和最小值,绿色候选表示当前最优来源;相等候选可以同时高亮,不额外累计方案数。格子下方的“+c”记录一种最优来源的最后一枚面额,动画按它回溯并展示一种最优组合;多个最优候选中选择较小的面额。
  • 加载后自动初始化,修改参数后点击“初始化”;每点一次“下一步”只计算一个正金额,支持自动播放、暂停、调速、直接完成、重置与全屏。暂停让当前金额完整算完后停止;直接完成立即求出剩余金额;重置或重新初始化会中断旧任务。进度统计不包含金额0。
  • 新版可输入1至6个正整数面额,面额最大为2147483647,目标金额为0至40。面额去重并递增展示,不影响最少枚数。目标上限是动画的显示限制,正文算法仍按原题范围处理。非法输入会提示修改并停止旧演示,不会将小数或负数悄悄转换为有效参数。

可用 [2]、目标3核对无解;用 [1]、目标0核对空选择需要0枚;用 [1,3,4]、目标6核对最优值2优于贪心的3。

每点“下一步”计算一个金额,支持暂停、自动播放和最优组合恢复。

主示例:逐个金额计算

coins = [1, 2, 5]、amount = 11,不可达标记为12。初始时dp[0]=0,其余位置都是12。

金额s最后一枚为1的候选最后一枚为2的候选最后一枚为5的候选dp[s]
11——1
221—1
322—2
432—2
53311
62322
73222
83333
94333
104422
113433

候选值是“剩余金额的最少枚数+1”,不是剩余金额本身;横线表示面额超过当前金额。

最终状态表为:

金额:0  1  2  3  4  5  6  7  8  9  10  11
枚数:0  1  1  2  2  1  2  2  3  3   2   3

最后一个状态具体为:

dp[11]=min⁡(dp[10]+1, dp[9]+1, dp[6]+1)=min⁡(3,4,3)=3. dp[11]=\min(dp[10]+1,\ dp[9]+1,\ dp[6]+1) =\min(3,4,3)=3.

例如从金额10的两枚5元继续加一枚1元,就得到 5 + 5 + 1。这是解释答案的一种组合,主程序不额外存储具体方案。

无解示例:把可达性信息保留下来

coins = [2]、amount = 3,不可达标记为4:

金额0123
买包子的可达性canTrueFalseTrueFalse
本题的最少枚数dp0不可达1不可达

金额3只能尝试“金额1再加一枚2元”,但金额1不可达,所以dp[3]保留标记4,函数最终返回−1。

这说明从买包子的布尔状态转为最小值状态后,仍能判断无解,并且为可达金额补充了最少使用次数。

复杂度分析

设面额数为n,目标金额为A,按整数加法、比较和列表访问为常数时间计:

项目复杂度依据
时间O(n(A+1))O(n(A+1));当A>0时通常写为 O(nA)O(nA)初始化A+1个状态,逐个金额比较n种面额
辅助空间O(A+1)O(A+1)保存0到A的最少枚数,无递归栈

题目给出的n≤12、A≤10000,最多进行120000次面额候选检查。只需计算到指定目标A,不需要为所有可能的正整数确定统一上界。

该算法的工作量与金额的数值A有关,而非只与A的二进制位数有关,属于伪多项式时间算法。上述空间不包含输入列表,也不包含本题没有要求的路径恢复数据。

动画的教学扩展另存长度为A+1的来源表,仍为 O(A+1)O(A+1) 量级;恢复k枚硬币的组合需要 O(k)O(k) 时间与输出空间。由于面额为正,回溯金额严格减少,且k≤A;零金额的结果为空组合,不可达时不回溯。

易错点

常见错误正确理解与修正
直接照搬买包子的布尔状态布尔值只说明能否凑出,比较最少枚数需要保存数值
用 dp[s] += dp[s - coin]这在累计计数,本题应取最小候选枚数
将全部dp初始化为0正金额会被误判为无需硬币;只有dp[0]初始化为0
忘记候选中的加1子状态不包含最后新增的这枚硬币
不检查coin≤s剩余金额可能为负,Python负下标还可能掩盖错误
无解状态在内部使用−1后直接参与min−1会被误当成更优值;内部用大标记,返回时再转为−1
认为最大面额优先一定最优[1,3,4]凑6时,3+3优于4+1+1
将每种面额的使用次数限制为一次本题每种无限,必须允许在较小金额的结果上继续追加
把最大公约数为1当成每个目标都可达[3,4]的最大公约数为1,但金额5仍然不可达
把“无穷多个金额凑不出”当成当前目标无解[2,4]虽有无穷多个奇数无法凑出,金额6仍可用2枚凑出

课堂练习

基础核对

写出下列输入的返回值,并说明其中一个与买包子可达性状态的对应关系。

coinsamount
[1,2,5]11
[2]3
[1]0
[2,4]6
[3,4]5
[7]14
参考答案

依次为 3、−1、0、2、−1、2。

例如 [7] 凑14时,买包子的可达性为True,本题进一步给出至少需要2枚;[2]凑3时,可达性为False,本题返回−1。

过程推演

给定 coins = [1,3,4]、amount = 6:

  1. 写出dp[0]到dp[6]。
  2. 展开dp[6]的三个候选。
  3. 比较动态规划与“每次优先最大面额”的结果。
参考答案

完整状态表为 [0, 1, 2, 1, 1, 2, 2]。

dp[6]=min⁡(dp[5]+1, dp[3]+1, dp[2]+1)=min⁡(3,2,3)=2. dp[6]=\min(dp[5]+1,\ dp[3]+1,\ dp[2]+1) =\min(3,2,3)=2.

最优组合为 3+3,共2枚;最大面额优先会选 4+1+1,共3枚。因此本题不能用这一贪心策略替代候选比较。

进阶思考

  1. 对同样的 [1,2,5] 和目标5,买包子的可达性子问题、本题、零钱兑换分别回答什么?
  2. 所有面额的最大公约数为g时,能怎样提前判断一部分无解目标?目标是g的倍数就一定有解吗?
  3. 把主实现改成“面额在外、金额正序在内”为什么仍然正确?能把同样的交换结论用于组合计数吗?
参考答案
  1. 分别回答True、1、4。它们表示能够凑出、最少使用一枚5元、共有四种不同的面额数量组合。
  2. 若g不能整除目标,必定无解,因为面额的任意整数倍之和都是g的倍数。但整除只是必要条件,不保证非负整数解存在。例如 [4,6] 的g=2,目标2能被g整除,却无法凑出。
  3. 每轮只增加一种可用面额,更新前的dp[s]保留不用当前面额的最优值;正序更新的dp[s−coin]允许包含当前面额,再加一枚便覆盖使用当前面额的候选,取min得到本轮最优值。不同路径重复比较不会改变最小值。组合计数采用加法,重复顺序会增加结果,所以不能照搬这一结论。
上次编辑于:
贡献者: zlzhou,liu-zhe,zilizhou