Project Euler 31

問題

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031

回答

再帰使えってっことですね。わかります。

def count_methods(target, coins):
  if len(coins) == 0:
    return 1
  else:
    s = 0
    c = coins[0]
    q = (target // c) + 1
    for i in range(0,q):
      s += count_methods(target - c * i, coins[1:])
    return s
    
def main():
  TARGET = 200
  COINS = [200,100, 50, 20, 10, 5, 2]
  print count_methods(TARGET,COINS)

main()