http://projecteuler.net/problem=31

http://projecteuler.net/thread=31;page=2 # 17 Feb 2006 04:08 pm
@Cached
def nway( total, coins): #recursive:
    if not coins: return 0 ## ???
    c, coins = coins[0], coins[1:]
    count = 0
    if total % c == 0: count += 1
    for amount in xrange( 0, total, c):
        count += nway(total - amount, coins) #?
    return count
# main
print nway( 200, (1,2,5,10,20,50,100,200))
# 18 Feb 2006 01:56 pm
def gencount( coins): #NOTE: an amount must be positive
  if len( coins) == 0: return lambda i0: 0
  if len( coins) == 1: return lambda i0: int( i0 % coins[0] == 0)
  
  coins = sorted(coins, reverse=True)
  code = 'lambda i0: sum(( 1'
  for i, c in enumerate(coins[:-1]):
    code += ' for i%d in xrange( i%d, -1, -%d) ' %\
            ( i+1, i, c)
  if coins[-1] != 1: code += ' if i%d %% %d == 0' % ( i+1, coins[-1] )
  code += ' ))'
  return eval( code)
print gencount( ( 1, 2, 5, 10, 20, 50, 100, 200 ))( 200) # 73682 0.028 seconds
# 25 May 2006 07:15 pm
def nways(n,coins): # dynamic programming:
    m = len(coins)
    
    ways = []
    for i in range(n+1):
        ways.append([0 for j in range(m+1)]) #?
    # initialize base cases
    for i in range(n+1):
        ways[i][0] = 0
    for j in range(m+1):
        ways[0][j] = 1
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            ways[i][j] += ways[i][j-1]
            if i>=coins[j-1]:
                ways[i][j] += ways[i-coins[j-1］[j]
    return ways[n][m]
print nways(200,[1,2,5,10,20,50,100,200])