Dynamic programming implementation of change counting problem

change.py

#!/usr/bin/env python3

def ways(amount, coins):

    # Set up our data. Note that this is all we need other than three
    # local variables we use in the loop below.
    starts = [ i + 1 + sum(coins[:i]) for i in range(len(coins)) ]
    data   = [ int(i in starts) for i in range(sum(coins) + len(coins) + 1) ]

    # Iterate up to the desired amount.
    for _ in range(amount):
        prev = 0
        for s, c in zip(starts, coins):
            # Shift old data down (up?) and compute new value for this
            # amount and subset of coins.
            data[s+1:s+c+1] = data[s:s+c]
            data[s]         = data[prev] + data[s+c]
            prev            = s

    # And there's the answer. Ta Da!
    return data[starts[-1]]

if __name__ == '__main__':

    from sys import argv

    amount = int(argv[1])
    coins  = [ int(x) for x in argv[2:] ]

    print(ways(amount, coins))