Project Euler Problem 031

http://projecteuler.net/index.php?section=problems&id=31
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031

In England the currency is made up of pound, e, and pence, p, and there are eight coins in general circulation:

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

It is possible to make e2 in the following way:
 
  1*e1 + 1*50p + 2*20p + 1*5p + 1*2p + 3*1p

How many different ways can e2 be made using any number of coins?

両替問題、うろ覚えでコードを書いたけどかなり遅い。

数を求めるだけなので、もうちょっと良い方法がありそうだけど、全然頭が回らなかった。。

import datetime


def count_change_ways(L, n):
    def f(n, k=0):
        result = 0
        
        n -= k
        if n == 0:
            return 1
        
        for m in L:
            if n >= m >= k:
                result += f(n, m) 
        
        return result
    
    return f(n)


def euler031():
    L = [ 1, 2, 5, 10, 20, 50, 100, 200 ]
    print count_change_ways(L, 200)


begin = datetime.datetime.now()
euler031()
end = datetime.datetime.now()
print end - begin

答え: 73682
実行時間: 5.076193秒くらい