在恒定时间内换硬币的方法有多少？

Question

假设我有三种类型的硬币——一分钱 (0.01)、一分钱 (0.05) 和一角钱 (0.10)，我想找到兑换一定金额的方法的数量。例如更改 27 美分：

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

解决此问题的一种更常见的方法是递归/动态地：找到在没有特定硬币的情况下进行更改的方法数量，然后减去该硬币数量并找到使用该硬币进行更改的方法。

但是，我想知道是否有办法使用缓存值和 mod 运算符来做到这一点。例如：

1. 10 美分可以通过 4 种方式更改：

   • 10 便士
   • 1 角钱
   • 2 镍
   • 1 镍，5 便士

2. 5 美分可以通过两种方式更改：

   • 1 镍
   • 5 便士

3. 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

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

首先让我们看一下 10 的倍数。例如n=20美分，前 10 美分可以通过 4 种方式更改，第二组 10 美分也可以。这将产生 4x4 = 16 种改变方式。但并非所有组合都是不同的：前 10 美分为 10 美分，后 10 美分为 10 便士，这与前 10 美分为 10 便士，后 10 美分为 10 美分。所以我们必须以有序的方式计算可能性：这将给出(n/10+3) choose 3可能性。但计数中的所有可能性仍然不同：为第一组和第二组 10 美分选择 5 分硬币和 5 分硬币，与为第一组选择 2 分镍币和为第二组选择 10 美分得到的零钱相同。再想一想，就会发现 1 镍币和 5 便士的可能性只能选择一次。因此，我们得到了(n/10+2) choose 2没有镍币/便士分割的找零方式（即镍币总数为偶数）和((n-10)/10+2) choose 2一镍币/便士分割的找零方式（即镍币总数为奇数）。

对于任意数量n的美分，让[n/10]表示向下舍入的值n/10，即可以在找零时使用的最大一角硬币数量。超过 10 英寸最大倍数的美分最多n只能通过两种方式进行兑换：要么全部换成便士，或者如果至少还剩下 5 分，则换成 1 镍币，其余的则换成便士。为了避免多次以相同的方式计算零钱，如果“多余”的零钱中有一枚五分钱，则可以禁止再使用任何便士（对于 10 美分的一组），因此只能使用 10 分和 5 分的硬币。 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。