YGC

PE31-Coin Sums

2 min read

题目

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p). It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?

解答

总量N的钱，有m种硬币，总的计数以C(N, m)表示。

那么：

  1. 如果解法中不包含第m种硬币, Sm，那么问题就变成C(N, m-1)。
  2. 如果解法中包含了第m种硬币，那么问题就变成了C(N-Sm, m)

所以把这两种情况考虑进来，问题就可以变成：

C(N, m) = C(N, m-1) + C(N-Sm, m)

这就是一个典型的递归了。那我们就要看递归退出的条件了。

  • 如果N = 0，已经没钱剩下了，那就是得到解了，返回1.
  • 如果N < 0，那就是没解了，返回0
  • 如果N >= 1，但是m ⇐0，也就是都没有硬币了。那也是没解，返回0

Python

def count_coins(N, m):  
    if N < 0 or len(m) <= 0:  
        return 0  
    if N == 0:  
        return 1  
  
    return count_coins(N, m[:-1]) + count_coins(N-m[-1], m)  
  
def solution31():  
    coins = [1,2,5,10,20,50,100,200]  
    return count_coins(200, coins)

R R版本是一样的：

count_coins <- function(N, m) {     
    n <- length(m)     
    if (N < 0 || length(m) <= 0)         
        return(0)     
    if (N == 0)         
        return(1)     
    return(count_coins(N, m[-n]) + count_coins(N-m[n], m)) }

答案

>>> solution31()  
73682

Graph View