Tabulation

Tabulation fills the table of answers with loops, smallest states first, instead of with recursive calls. It has no depth limit, it is usually faster, and it makes it easy to keep only the part of the table that is still needed.

Fill in a safe order

A loop has to choose the order of the states itself. The order is safe if every state comes after all the states its rule reads. In the DAG of lesson 1 (states as points, arrows to the states each one uses), that means following the arrows backwards. Such an order is called a topological order (GRPH-5 finds one for any DAG). For most DP problems it is easy to see:

• an amount x uses smaller amounts, so go from 0 upwards (GRDY-5’s fewest-coins loop does this);
• a grid cell uses the cell above and the cell to its left, so go row by row, left to right;
• a suffix (the items from i to the end) uses shorter suffixes, so go from the end backwards.

Row by row

Here is lesson 2’s grid count as a loop. Step through the first version of the figure.

def grid_paths(rows, cols):
    paths = [[1] * cols for _ in range(rows)]
    for r in range(1, rows):
        for c in range(1, cols):
            paths[r][c] = paths[r - 1][c] + paths[r][c - 1]
    return paths[rows - 1][cols - 1]

Each cell is filled once, from two cells that are already filled: O(rows × cols) time and no calls at all. The base cases (the top row and the left column) are set before the loop starts, here by filling the whole table with 1s.

Keep only what you need

Row r reads only row r − 1. So once row r is done, rows before r − 1 are never read again. Keeping two rows, or even one, is enough. The second version of the figure keeps one list and updates it in place: before row[c] is changed it still holds the value from the row above, and row[c - 1] to its left has already been updated.

def grid_paths(rows, cols):
    row = [1] * cols                   # row 0
    for _ in range(1, rows):
        for c in range(1, cols):
            row[c] += row[c - 1]       # above + left
    return row[-1]

The time is unchanged and the space drops from O(rows × cols) to O(cols). Fibonacci with two names (RECR-6) is the same idea with a row of length 2. Before doing this, check two things:

• The direction of the inner loop. Updating in place is right only if every cell read is either an old value that has not been overwritten yet, or a new value that should be read. Lesson 8 shows a case where going the wrong way gives a different answer.
• Whether you need the choices. Rebuilding the answer itself, not just its value, needs the old rows (lesson 9).

Pulling and pushing

The loops above pull: each state reads the states it depends on. The other way is to push: when a state’s answer is final, add it to every state that uses it. Counting the ways up the footbridge of RECR-P2 (moves of 1, 2 or 3 steps), pushed:

def ways_up(n):
    ways = [1] + [0] * n
    for i in range(n):                 # ways[i] is final here
        for step in (1, 2, 3):
            if i + step <= n:
                ways[i + step] += ways[i]
    return ways[n]

Both give the same answers. Pushing is easier when it is simpler to list where you can go from a state than where you could have come from, as in games and in walks on a grid with unusual moves.

Memoisation or tabulation?

A good habit: write the memoised version first, because it follows the rule directly, and test it on small inputs. If the inputs are large, turn it into a table. Use memoisation for good when the needed states are few and scattered (lesson 2’s f(n // 2) + f(n // 3)), or when the order is hard to see.

Now try DYNP-P3, Ways to decode, where the input is far too long for recursion.