Project Euler #31

euler31.py

amount = 200
coins = (200, 100, 50, 20, 10, 5, 2, 1)
ways = [1] + [0] * amount

# dynamic programing (quick)
for coin in coins:
    for i in range(coin, amount + 1):
        ways[i] += ways[i - coin]

print ways[amount]

# recursive (slower)
def ways(amount, coins):
    if amount == 0:
        return 1
    elif len(coins) == 0:
        return 0
    else:
        return sum((ways(amount - i * coins[0], coins[1:])
                    for i in range(amount / coins[0] + 1)))

print ways(amount, coins)