# Any way to optimize this already fast Python solution to Project Euler 31 (coin sums)?

This is a Python solution for all general cases. Any suggestions at all would be appreciated; in my opinion it's already quite good! Here's a link to the problem.

from timeit import default_timer as timer

def count_coins(target, operands):
ways_to_make = [1] # list of ways to make x at index x
for o in range(0, len(operands)):
for t in range(target + 1):
# initialise undefined target
if len(ways_to_make) <= t:
ways_to_make.append(0)
# add ways to make number recursively
if t >= operands[o]:
ways_to_make[t] += ways_to_make[t - operands[o]]

return ways_to_make[target]

start = timer()
ans = count_coins(200, [1, 2, 5, 10, 20, 50, 100, 200])
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)


It will be faster if you pre-generate the ways_to_make array:

def count_coins(sum, coins):
ways_to_make = [0 for _ in range(sum + 1)]
ways_to_make[0] = 1
for coin in coins:
for t in range(sum + 1):
if t >= coin:
ways_to_make[t] += ways_to_make[t - coin]

return ways_to_make[sum]


This doesn't waste memory because you would allocate those elements anyway, and it's a lot faster to create a larger list once than extending it in every loop iteration. Not to mention that this gets rid of an if statement.

I also changed the for o in range(len(coins)) loop to the more intuitive for coin in coins. In my measurements this gave an extra speed boost too.

Finally, I took the liberty to rename your function parameters to more meaningful names.

The inner loop

for t in range(sum + 1):
if t >= coin:
ways_to_make[t] += ways_to_make[t - coin]


can be written better as

for t in range(coin, sum + 1):
ways_to_make[t] += ways_to_make[t - coin]


It becomes automatically clear that here t >= coin