Classic dynamic programming question


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]

                table[idx_c][idx_a] = table[idx_c - 1][idx_a]

    return max([x for sublist in table for x in sublist])
assert(ways_to_make_change(coins, total)) == 4

[Challenge] Change Please