Dynamic programming: fill a table from the bottom up

A machine has to pay out 6 using coins worth 1, 3 and 4, with as few coins as it can. The obvious plan is to take the biggest coin that fits, again and again: 4, then 1, then 1. Three coins. Yet 3 + 3 makes 6 with only two.

You could try every combination of coins, but the combinations multiply as the amount grows. The memoization lesson ended with a better way: write the answers to the smaller questions into a table, filled from the bottom up, so that each one is worked out once. This lesson shows how to design that table for a problem made of overlapping smaller ones, and how to fill it with a plain loop. That is dynamic programming.

state

What one cell of the table means, in words. In coin change, dp[a] is the fewest coins that add up to exactly a.

recurrence

The rule that builds a cell from other cells, such as dp[a] = 1 + the smallest dp[a − c] over the coins c that fit.

base case

A cell whose answer is known without the rule, such as dp[0] = 0, since making 0 takes no coins. Every other cell grows from it.

fill order

The order the cells are filled in. Each cell must come after every cell its recurrence reads.

bottom-up (tabulation)

Filling the table in a loop from the base cases up, instead of recursing from the top and remembering answers on the way back, as memoization does.

Think about the last coin in the best way to make 6. It is a 1, a 3 or a 4, and whichever it is, the coins before it must make what is left (5, 3 or 2) with as few coins as possible. So if the table already holds the fewest coins for every smaller amount, dp[6] is one more than the smallest of dp[5], dp[3] and dp[2]. The same holds for every amount, so the table can be filled from 0 upwards.

The order is what makes it work. Every dp[a − c] is a smaller amount than a, so by the time the loop reaches a, it is already final. Each amount is worked out once, from answers that are already there, and nothing waits on a recursive call.

The same four decisions work on a grid, for a question that counts. A robot steps only right or down: how many paths lead from the top-left corner to the bottom-right? Let P[i,j] be the number of paths that reach cell (i, j). Every path into a cell arrives from the cell above or the cell to its left, so P[i,j] = P[i−1,j] + P[i,j−1]. There is one way to be at the start, so P[0,0] = 1, and every cell in the top row or the left column can be reached only one way. Filling row by row, left to right, has both neighbours ready in time.

Look at what each recurrence does with its candidates. Unique paths adds them: a path through the cell above and a path through the cell to the left are different paths, so both count. Coin change keeps the smallest, because it wants one best answer, not all of them. Counting questions (how many ways?) add up the ways in; optimising questions (the fewest, the most, the cheapest) keep the best candidate.

Here is an optimising question that keeps the largest candidate. A street of houses holds 5, 9, 6, 1, 8 and 7, and a robber wants the most money without ever robbing two houses next door. The four decisions:

• State: dp[i] is the most money from houses 1 to i alone.
• Base cases: dp[0] = 0 (no houses) and dp[1] = 5 (rob the only house).
• Recurrence: at house i, either skip it and keep dp[i − 1], or rob it and add its value to dp[i − 2], since its neighbour must then be skipped: dp[i] = max(dp[i − 1], v[i] + dp[i − 2]).
• Fill order: left to right, so both earlier totals are ready.

Before each house is filled in, predict whether robbing it beats skipping it. Then, walking back from the last house, say which houses were robbed.

Here is coin change as two loops. The table starts with dp[0] = 0 and every other amount at amount + 1, which stands in for ∞: no real answer needs more than amount coins, because every coin is worth at least 1. Then, for each amount from 1 up, each coin that fits offers dp[a − c] + 1, and the smallest offer stays. If dp[amount] is still amount + 1 at the end, no coins make it, and the function returns -1.

def fewest_coins(coins, amount):
    too_many = amount + 1
    dp = [too_many] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    if dp[amount] == too_many:
        return -1
    return dp[amount]

print(fewest_coins([1, 3, 4], 6))

This finds exactly the answers a memoised recursion would: the same subproblems and the same recurrence. What differs is how it runs. For n coins and a target amount A, the loop fills every amount from 1 to A and tries every coin at each, so it takes O(n·A) time and O(A) memory, and it never recurses. A memoised version asked for 10,000 with a 1 coin would recurse thousands of calls deep, past Python’s default limit of 1,000. Top-down has one edge in return: it solves only the amounts it actually reaches, while bottom-up fills them all.

Amounts that can't be made are where ∞ matters. If every coin that fits leaves an amount that can't be made, this amount can't be made either: one more coin on top of impossible is still impossible, ∞ + 1 = ∞.

Each recurrence also says which cells it reads, and that decides how much of the table you must keep. House robber reads only the last two totals, so two variables can slide along the street: O(1) memory. Unique paths reads only the row above and the cell to the left, so one row, updated in place, is enough. Keep the whole table when you need to walk back through it to recover the choices, the coins used or the houses robbed, as every visualiser here does.

• Dynamic programming fills a table of subproblem answers so that each one is solved once. It takes four decisions: the state (what a cell means), the recurrence, the base cases and the fill order.
• The fill order must put every cell after the cells it reads: amounts upwards for coin change, rows from the top for unique paths, houses left to right for house robber.
• Counting questions add up the ways in (unique paths); optimising questions keep the best candidate: the smallest for coin change, the largest for house robber.
• It gives the same answers as memoization, in a loop with no recursion depth. When cells read only the last one or two cells or the row above, keep just those.
• A greedy choice can fail where the table doesn't: largest-coin-first makes 6 from 1, 3 and 4 with three coins, and the table finds two.
• Next: dynamic programming on sequences, where the table compares two strings cell by cell (try the edit distance visualiser), and all-pairs shortest paths, where Floyd–Warshall allows one more stop-over node at a time. Practise with Fewest Coins for an Amount, Rob a Row of Houses and Count Paths Across a Grid, or fill the table yourself in Count the paths through a grid. The 0/1 knapsack uses the same recipe on a table of items and capacities.