gistfile1.py

def pe31(n=200):
    coin = (1, 2, 5, 10, 20, 50, 100, 200)
    ncoin = len(coin)
    cnt = [[0] * (n+1) for _ in xrange(ncoin+1)]
    cnt[0][0] = 1
    for i in xrange(1, ncoin+1):
        for j in xrange(n+1):
            for k in xrange(j / coin[i-1] + 1):
                cnt[i][j] += cnt[i-1][j - k*coin[i-1]]
    return cnt[-1][-1]