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

Question

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)

Answer 1

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.

Answer 2

I will add a bit to janos's answer.

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