Coin Change
你会得到一个包含不同硬币面值的列表 coins 和一个目标 amount。每种面值的硬币都可以使用任意次。请返回面值之和恰好等于 amount 的最少硬币数；如果无法凑出该金额，则返回 -1。金额为 0 时需要 0 枚硬币。
函数
- coinsinteger-array
- 不同面值的硬币，每种都可以使用任意次数
- amountinteger
- 应付总额，准确无误
- 返回值integer
- 所需硬币数最少；如果无法凑出该金额，则返回 -1
约束条件
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- 所有硬币的面值都不同。
示例
- 输入
- coins = [2, 5, 10]amount = 27
- 输出
- 4
- 解释
- 用 4 枚硬币组成 10 + 10 + 5 + 2，结果是 27。用 3 枚硬币无法组成：27 是奇数，所以必须恰好用 1 枚 5，另外 2 枚最多只能组成 20，不够 22。
- 输入
- coins = [4, 6]amount = 7
- 输出
- -1
- 解释
- 两个硬币的面值都是偶数，所以你能凑出的总额都是偶数。7 是奇数，所以答案是 -1。
- 输入
- coins = [3, 7]amount = 0
- 输出
- 0
- 解释
- 支付 0 不需要任何硬币，所以无论硬币的面值是多少，答案都是 0。
进阶
你能计算出有多少种不同的硬币组合可以凑成 amount，而不是找出所需硬币数量最少的组合吗？
提示
逐个打开提示，每个都会多透露一点。
总是选择能凑出的最大面额硬币，不一定能用最少的硬币。试试硬币
[1, 3, 4]和金额6。假设你已经知道每个小于
t的金额所需的最少硬币数。再加一枚硬币，可以从哪些较小的金额凑出t？从
0开始向上填充表fewest[0..amount]：fewest[0] = 0，对于每个fewest[t]，都要在硬币c <= t中找到最优的fewest[t - c]，然后加上1。将无法达到的金额标记为一个大于任何实际答案的值，例如amount + 1，最后将其转换为-1。
题解
每次都选能用的最大面额硬币，这种方法会失败：面额为 1、3 和 4 的硬币支付 6 时，需要 4 + 1 + 1，而 3 + 3 只需要两枚硬币。凑出某个金额所需的最少硬币数，只取决于凑出更小金额所需的最少硬币数，因此你要从 0 到 amount，逐个计算每个金额。
用递归尝试所有组合
结果正确，但无法在最大的测试中运行完毕
思路
如果你最后支付的硬币面值是 c，那么在它之前支付的硬币需要以尽可能低的成本凑出 remaining - c。因此，对每一种可以凑出金额的硬币，fewest(remaining) 都是 fewest(remaining - c) 的最优结果再加 1。这个方法会尝试所有不会超出目标金额的硬币组合，因此不会漏掉最优解。
它会反复计算相同的金额。使用面值为 2、5 和 10 的硬币时，金额 27 在支付 10 + 2、2 + 10、5 + 5 + 2 等不同顺序后都会得到 15，并且每次都会从头计算 15。调用次数会随着金额的增大而呈指数增长。
算法
- 编写一个辅助函数
fewest(remaining)，返回凑出remaining所需的最少硬币数；如果没有可行方案，则返回 -1。 - 如果
remaining是 0，则返回 0。 - 对于每种不大于
remaining的硬币，调用辅助函数，计算付出这枚硬币后剩余金额所需的硬币数。 - 保留不为 -1 的最小结果，再加上付出的这枚硬币。
- 返回这个硬币数；如果每种硬币都无法凑出金额，则返回 -1。答案是
fewest(amount)。
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)使用记忆化的递归
结果正确，但无法在最大的测试中运行完毕
思路
递归只会询问从 0 到 amount 的金额。第一次算出某个答案时，将它存入数组；再次遇到该金额时，返回存储的值。每个金额只需通过遍历硬币计算一次：工作量为 O(amount × coins)。
每支付一枚硬币，调用仍会嵌套一层。如果有一枚面值为 1 的硬币，嵌套层数最多可达 10^4，这超过了许多语言默认调用栈的容量。
算法
- 创建一个数组
memo，为从 0 到amount的每个金额预留空间，并存入一个表示尚未计算的标记。 - 在
fewest(remaining)中，遇到 0 时返回 0；如果memo[remaining]中已有答案，则返回该答案。 - 否则，像普通递归那样尝试每个适用的硬币，并保留最小结果再加 1。
- 返回前，将结果（包括 -1）保存到
memo[remaining]中。 - 返回
fewest(amount)。
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)按金额进行自底向上的动态规划
思路
从 0 开始向上填充表 fewest。当你计算到总额 t 时，所有更小的总额都已经确定，因此 fewest[t] 等于所有能凑出该总额的硬币 c 对应的 fewest[t-c] 中最小值加 1。
无法用任何硬币组合凑出的总额会保留标记值 amount + 1。每枚硬币的面值至少为 1，因此真实答案使用的硬币不会超过 amount 枚，而标记值在每次比较中都会落败。用循环替代递归，因此调用栈的深度不再重要。
算法
- 创建一个包含
amount + 1个元素的fewest，并将所有元素都设为标记amount + 1，再将fewest[0]设为 0。 - 对于从 1 到
amount的每个总金额t，检查每个满足c ≤ t的硬币c。 - 如果
fewest[t-c] + 1小于fewest[t]，就将其存入fewest[t]。 - 循环结束后，如果
fewest[amount]仍然是标记，就返回 -1；否则返回fewest[amount]。
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
易错点和边界情况
- 先选面值最大的硬币。使用面值为 3 和 5 的硬币凑出金额 9 时，会先选 5 和 3，剩下 1 无法凑出，于是返回 -1；但 3 + 3 + 3 可以凑出 9。
- 使用最大的整数作为标记。给它加 1 会溢出并变成负数，于是在所有比较中都胜出。请使用
amount + 1。 - 给死路结果加 1。一个返回 -1 的分支，加上你付出的硬币后会得到 0，并在所有比较中胜出。请跳过结果为 -1 的分支。
- 递归
amount层。使用面值为 1 的硬币凑金额10^4时，Python 会在达到默认的 1000 层时停止，JavaScript、Dart、Ruby 和 R 也会耗尽栈空间。 - 当硬币面值大于
t时，在表的起始位置之前读取fewest[t-c]。
常见问题3
为什么贪心策略无法解决硬币找零问题？
只选择能用上的最大面额硬币，仅对某些硬币系统是可靠的，例如大多数现实中的货币系统。对于面额为 1、3 和 4 的硬币，凑出 6 需要 3 枚硬币，而不是 2 枚；对于面额为 3 和 5 的硬币，则根本无法凑出 9。动态规划会比较每一种选择，因此不会被任何硬币系统误导。
Coin Change 的时间复杂度是多少？
动态规划的解法需要 O(amount × coins) 时间和 O(amount) 空间：每个金额对应一个表项，并且每个表项都会检查每种硬币。不使用记忆化的纯递归，其时间复杂度会随金额呈指数级增长。
对于 Coin Change，采用自顶向下还是自底向上的方法更好？
两者完成的工作量相同，都是 O(amount × coins)。自顶向下的递归可能会嵌套到与金额相同的深度，在多种语言中，金额为 10^4 时会导致调用栈溢出。自底向上会用循环填充表格，因此没有深度限制，在面试中是更稳妥的选择。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def coinChange(coins, amount):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
coins = [2, 5, 10] amount = 27
预期输出
4