在恒定时间内改变硬币的方法有多少种？

Question

假设我有三种硬币——一便士 (0.01)、五分硬币 (0.05) 和一角硬币 (0.10)，我想找出找零的方法的数量。例如更改 27 美分：

change(amount=27, coins=[1,5,10])

解决这个问题的一种更常见的方法是 recursively/dynamically：找到没有特定硬币的情况下进行找零的方法的数量，然后扣除该硬币的数量并找到进行找零的方法用那个硬币。

但是，我想知道是否有一种方法可以使用缓存值和 mod 运算符来实现。例如：

10美分可以换成4种方式：
- 10 便士
- 1 角钱
- 2 分硬币
- 1 镍币，5 便士
5美分可以改变2种方式：
- 1 镍币
- 5 便士
1-4美分可以换1种方式：
- 1-4 便士

例如，这是错误的，但我的想法是：

def change(amount, coins=[1,5,10]):
    cache = {10: 4, 5: 2, 1: 1}
    for coin in sorted(coins, reverse=True):
        # yes this will give zerodivision
        # and a penny shouldn't be multiplied
        # but this is just to demonstrate the basic idea
        ways = (amount % coin) * cache[coin]
        amount = amount % ways
    return ways

如果是这样，该算法将如何工作？任何语言（或伪语言）都可以。

Answer 1

这将是解决此问题的 DP 方法之一：

def coin_ways(coins, amount):
    dp = [[] for _ in range(amount+1)]
    
    dp[0].append([]) # or table[0] = [[]], if prefer

    for coin in coins:
        for x in range(coin, amount+1):
            dp[x].extend(ans + [coin] for ans in dp[x-coin])
    #print(dp)
    
    return len(dp[amount])


if __name__ == '__main__':
    coins = [1, 5, 10]  #  2, 5, 10, 25]
    print(coin_ways(coins, 27))   # 12

Answer 2

预先计算 10 美分和 5 美分的找零可能性不能直接应用于更大的值，但对于特殊情况，例如给定的便士、五分硬币和 10 美分的例子，找零的数量公式当更详细地研究 5 美分和 10 美分的不同找零方式如何组合时，可以得出各种可能性。

让我们先看看 10 的倍数。 n=20美分，前10美分有4种变化方式，第二组10美分也可以。这将使 4x4 = 16 种改变方式。但并非所有组合都不同：前 10 美分为 10 美分，其他 10 美分为 10 便士，与前 10 美分为 10 美分，后 10 美分为 1 美分相同。所以我们必须按顺序计算可能性：这将给出 (n/10+3) choose 3 种可能性。但在这种计算中并非所有的可能性都是不同的：为第一组和第二组 10 美分选择 5 美分和 5 美分与为第一组选择 2 美分和为第二组选择 10 美分产生相同的变化。再仔细考虑一下，就会发现 1 镍和 5 便士的可能性应该只选择一次。因此，我们得到 (n/10+2) choose 2 种没有 nickel/pennies 分割的变化方式（即五分币的总数将是偶数）和 ((n-10)/10+2) choose 2 种 nickel/pennies 分割的变化方式（即镍的总数将是奇数）。

对于任意数量的 n 美分，让 [n/10] 表示向下舍入的值 n/10，即可以在零钱中使用的最大 10 美分硬币数。 n 中超过 10 的最大倍数的美分最多只能以两种方式更改：要么全部为便士，要么 - 如果至少剩余 5 美分 - 一镍币和其余的便士。如果 'excess' 美分的零钱中有五分硬币，则可以禁止使用任何更多的便士（对于 10 美分的一组），为了避免多次计算相同的零钱，所以只能使用一角硬币和五分硬币对于每组 10 美分，给出 [n/10]+1 种方式。

合起来得出N的公式如下，换n分的方式总数：

N1 = ([n/10]+2) choose 2  +  ([n/10]+1) choose 2  =  ([n/10]+1)^2

       [n/10]+1,  if n mod 10 >= 5
N2 = {
       0,         otherwise

N = N1 + N2

或作为 Python 代码：

def change_1_5_10_count(n):
  n_10 = n // 10
  N1 = (n_10+1)**2
  N2 = (n_10+1) if n % 10 >= 5 else 0
  return N1 + N2

顺便说一下，计算可以进一步简化：N = [([n/5]+2)^2/4]，或者用 Python 表示法：(n // 5 + 2)**2 // 4.

Answer 3

几乎肯定不是一般情况。这就是使用递归和自下而上动态程序的原因。模数运算符会在将金额除以硬币面额时为我们提供余数——这意味着我们将尽可能使用该硬币的最大数量——但对于我们的解决方案，我们需要计算不同时进行找零的方式使用每种硬币面额的计数。

可以通过使用不同的硬币组合来达到相同的中间数量，这就是经典方法使用缓存的目的。 O(amount * num_coins):

# Adapted from https://algorithmist.com/wiki/Coin_change#Dynamic_Programming
def coin_change_bottom_up(amount, coins):
  cache = [[None] * len(coins) for _ in range(amount + 1)]

  for m in range(amount+1):
    for i in range(len(coins)):
      # There is one way to return
      # zero change with the ith coin.
      if m == 0:
        cache[m][i] = 1

      # Base case: the first
      # coin (which would be last
      # in a top-down recursion).
      elif i == 0:
        # If this first/last coin
        # divides m, there's one
        # way to make change;
        if m % coins[i] == 0:
          cache[m][i] = 1
        # otherwise, no way to make change.
        else:
          cache[m][i] = 0

      else:
        # Add the number of ways to
        # make change for this amount
        # without this particular coin.
        cache[m][i] = cache[m][i - 1]

        # If this coin's denomintion is less
        # than or equal to the amount we're
        # making change for, add the number
        # of ways we can make change for the
        # amount reduced by the coin's denomination
        # (thus using the coin), again considering
        # this and previously seen coins.
        if coins[i] <= m:
          cache[m][i] += cache[m - coins[i]][i]

  return cache[amount][len(coins)-1]

Answer 4

使用 Python，您可以利用 @cache 装饰器（或 @lru_cache）并自动生成缓存解决方案的递归解决方案。例如：

from functools import cache

@cache
def change(amount, coins=(1, 5, 10)):
    if coins==(): return amount==0
    C = coins[-1]
    return sum([change(amount - C*x, coins[:-1]) for x in range(1+(amount//C))])

print(change(27, (1, 5, 10))) # 12
print(change(27, (1, 5))) # 6
print(change(17, (1, 5))) # 4
print(change(7, (1, 5))) # 2

# ch(27, (1, 5, 10)) == ch(27, (1, 5)) + ch(17, (1, 5)) + ch(7, (1, 5))

这将仅对那些尚未计算和存储结果的参数值调用递归。使用 @lru_cache，您甚至可以指定缓存中允许的最大元素数。

在恒定时间内改变硬币的方法有多少种？

Number of ways to change coins in constant time?

algorithm

optimization

combinations

coin-change