# Classic dynamic programming question

#1

Classic dynamic programming question. I have a 2 video series explaining
the construction of the table manually, then coding the algorithm previously done by hand, in python.

In the above case, the total represents the weight of a backpack and the item weights are analogous to coins, but it's the same rational.

``````coins = [1,2,5]
total = 5

# Dynamic programming solution
def ways_to_make_change(coins_list, total_amount):
table = [[0 for x in range(total_amount+1)]  for y in range(len(coins_list))]

# First column will be ones since there's 1 way to make zero change for all coins
for row in table:
row[0] = 1

# First iterate over the coins then iterate over the totals
for idx_c, coin in enumerate(coins_list):
for idx_a, amount in enumerate(range(total_amount+1)):
if coin <= amount:
table[idx_c][idx_a] = table[idx_c - 1][idx_a] + table[idx_c][amount - coin]
continue

else:
table[idx_c][idx_a] = table[idx_c - 1][idx_a]
continue

return max([x for sublist in table for x in sublist])

assert(ways_to_make_change(coins, total)) == 4``````