In [12]:

    

coins = [1, 2, 5, 10, 20, 50, 100, 200]
sum_ = 5
debug = True
counts = [0] * (sum_ + 1)
counts[0] = 1

for coin in coins:
    for i in range(coin, sum_ + 1):
            if debug is True:
                print('coin {} at {} with sum {} , add {}'.format(coin, i,  counts[i], counts[i-coin]))
            counts[i] += counts[i - coin]
    if debug:
        print('')

if debug is True:
    print(counts)
else:
    print(counts[-1])


    

    




coin 1 at 1 with sum 0 , add 1
coin 1 at 2 with sum 0 , add 1
coin 1 at 3 with sum 0 , add 1
coin 1 at 4 with sum 0 , add 1
coin 1 at 5 with sum 0 , add 1

coin 2 at 2 with sum 1 , add 1
coin 2 at 3 with sum 1 , add 1
coin 2 at 4 with sum 1 , add 2
coin 2 at 5 with sum 1 , add 2

coin 5 at 5 with sum 3 , add 1






[1, 1, 2, 2, 3, 4]

In [ ]: