硬币找零问题
硬币找零问题
中等 完全背包优化 Python“买包子”已经能判断一个数量能不能凑出。如果还要求“用的笼数最少”,状态需要怎样改变? 把蒸笼容量换成硬币面额,把布尔值换成最少枚数,就得到本题的思路。
本节学习目标
- 会迁移: 从买包子的可达性状态,转化为硬币找零的最小值状态。
- 会推导: 根据最后一枚硬币定义子问题,说明初始化、转移与不可达状态。
- 会核对: 跟踪金额递增的计算过程,区分可行性、最少枚数和组合数量。
题目描述
给定正整数列表 coins 表示可用的硬币面额,以及非负整数 amount 表示目标金额。每种面额的硬币数量无限,求恰好凑出目标金额所需的最少硬币枚数。
如果无法恰好凑出,返回−1;金额为0时,返回0。本题只返回最少枚数,不要求程序恢复具体硬币组合,也不统计组合数量。
交互动画另提供“恢复一种最优硬币组合”的教学扩展:记录各可达金额的最后一枚硬币,再从目标金额逐次扣减该面额,直到0。动画将面额去重并递增排列,候选相等时保留较小的最后一枚面额;Python主实现仍只返回最少枚数。
参数、范围与规则
| 项目 | 约定 |
|---|---|
| 面额列表 | coins,长度n满足 |
| 单个面额 | 正整数, |
| 目标金额 | 整数, |
| 使用次数 | 每种面额可使用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=0 | 0 | 不使用任何硬币即可 |
coins=[1,3,4], amount=6 | 2 | 使用3元、3元,比4元、1元、1元更少 |
最后一个例子也说明:每次优先拿最大面额的贪心策略,对任意面额集合不一定得到最优解。
题目分析
从买包子的“能否凑出”向前走一步
买包子中,每种蒸笼容量无限使用,先判断某个数量是否能够凑出,再统计指定范围或题目要求范围内的不可达数量。本题则给定一个目标,进一步比较各种凑法的使用次数。
| 对照项目 | 买包子的可达性子问题 | 硬币找零 |
|---|---|---|
| 每种规格 | 一笼包子数a | 一枚硬币面额c |
| 状态 | can[s]:能否凑出s | dp[s]:凑出s最少需要几枚 |
| 零状态 | can[0] = True | dp[0] = 0 |
| 暂不可达 | False | 无穷大 |
| 合并来源 | 有一个来源可达就可达 | 比较所有可达来源的使用枚数,取最小值 |
买包子可以从“s−a能够凑出”推出“再加一笼后s能够凑出”。本题保留更多信息:若s−c最少需要k枚,再加一枚c,就得到凑出s的一种k+1枚方案。
因此,最小值状态也包含可达性信息:dp[s] 有限就表示可达;只有布尔值时,则无法判断两种可行方案谁用的硬币更少。
定义状态与边界
定义 dp[s]:使用给定的全部面额,恰好凑出金额s所需的最少硬币枚数。 暂时无法凑出时,记为无穷大。
这里的0表示需要0枚硬币,不是有0种方案。金额0在组合计数问题中有一种空组合,但在本题中它的最少使用枚数为0。
也可以用数量向量表示本题:设第i种面额为 ,其使用枚数为非负整数 ,其中 ,目标为:
根据最后一枚硬币推导转移
对于正金额s,假设最后加入的一枚硬币面额为c:
- 必须有c≤s,否则剩余金额为负数。
- 去掉这枚硬币,剩下的金额为s−c。
- 若s−c可达,则当前候选需要
dp[s - c] + 1枚。 - 比较所有合法面额的候选,取最少枚数。
得到:
无合法面额或所有来源均不可达时,状态仍为无穷大。由于所有面额为正数,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] |
|---|---|---|---|---|
| 1 | 1 | — | — | 1 |
| 2 | 2 | 1 | — | 1 |
| 3 | 2 | 2 | — | 2 |
| 4 | 3 | 2 | — | 2 |
| 5 | 3 | 3 | 1 | 1 |
| 6 | 2 | 3 | 2 | 2 |
| 7 | 3 | 2 | 2 | 2 |
| 8 | 3 | 3 | 3 | 3 |
| 9 | 4 | 3 | 3 | 3 |
| 10 | 4 | 4 | 2 | 2 |
| 11 | 3 | 4 | 3 | 3 |
候选值是“剩余金额的最少枚数+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
最后一个状态具体为:
例如从金额10的两枚5元继续加一枚1元,就得到 5 + 5 + 1。这是解释答案的一种组合,主程序不额外存储具体方案。
无解示例:把可达性信息保留下来
coins = [2]、amount = 3,不可达标记为4:
| 金额 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 买包子的可达性can | True | False | True | False |
| 本题的最少枚数dp | 0 | 不可达 | 1 | 不可达 |
金额3只能尝试“金额1再加一枚2元”,但金额1不可达,所以dp[3]保留标记4,函数最终返回−1。
这说明从买包子的布尔状态转为最小值状态后,仍能判断无解,并且为可达金额补充了最少使用次数。
复杂度分析
设面额数为n,目标金额为A,按整数加法、比较和列表访问为常数时间计:
| 项目 | 复杂度 | 依据 |
|---|---|---|
| 时间 | ;当A>0时通常写为 | 初始化A+1个状态,逐个金额比较n种面额 |
| 辅助空间 | 保存0到A的最少枚数,无递归栈 |
题目给出的n≤12、A≤10000,最多进行120000次面额候选检查。只需计算到指定目标A,不需要为所有可能的正整数确定统一上界。
该算法的工作量与金额的数值A有关,而非只与A的二进制位数有关,属于伪多项式时间算法。上述空间不包含输入列表,也不包含本题没有要求的路径恢复数据。
动画的教学扩展另存长度为A+1的来源表,仍为 量级;恢复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枚凑出 |
课堂练习
基础核对
写出下列输入的返回值,并说明其中一个与买包子可达性状态的对应关系。
| coins | amount |
|---|---|
[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:
- 写出dp[0]到dp[6]。
- 展开dp[6]的三个候选。
- 比较动态规划与“每次优先最大面额”的结果。
参考答案
完整状态表为 [0, 1, 2, 1, 1, 2, 2]。
最优组合为 3+3,共2枚;最大面额优先会选 4+1+1,共3枚。因此本题不能用这一贪心策略替代候选比较。
进阶思考
- 对同样的
[1,2,5]和目标5,买包子的可达性子问题、本题、零钱兑换分别回答什么? - 所有面额的最大公约数为g时,能怎样提前判断一部分无解目标?目标是g的倍数就一定有解吗?
- 把主实现改成“面额在外、金额正序在内”为什么仍然正确?能把同样的交换结论用于组合计数吗?
参考答案
- 分别回答True、1、4。它们表示能够凑出、最少使用一枚5元、共有四种不同的面额数量组合。
- 若g不能整除目标,必定无解,因为面额的任意整数倍之和都是g的倍数。但整除只是必要条件,不保证非负整数解存在。例如
[4,6]的g=2,目标2能被g整除,却无法凑出。 - 每轮只增加一种可用面额,更新前的dp[s]保留不用当前面额的最优值;正序更新的dp[s−coin]允许包含当前面额,再加一枚便覆盖使用当前面额的候选,取min得到本轮最优值。不同路径重复比较不会改变最小值。组合计数采用加法,重复顺序会增加结果,所以不能照搬这一结论。
