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

[Challenge] Change Please