Fill the Table

A memo fills up in whatever order the questions happen to be asked. Look at it afterwards and you will usually find a tidy thing: an answer for every stair from 2 to n, or for every crossing of a grid. If you know in advance which answers will be needed, and you can put them in an order where each one only needs earlier ones, you can skip the calls altogether. Make a table, and fill it in.

Before this, you can: remember answers in a dictionary, and say what the key must hold; use a list of lists as rows and columns; count the work as the number of different questions.

By the end you will be able to turn a remembered function into a table, choose an order of filling in which nothing is read before it is ready, build a table with rows and columns, walk back through a table to find the choices behind the best value, keep only the part of a table that is still needed, and decide between a memo and a table.

Before you read on, decide what this prints:

table = [1, 1]
for stair in range(2, 9):
    table.append(table[stair - 1] + table[stair - 2])
print(table)
print(table[8])

[1, 1, 2, 3, 5, 8, 13, 21, 34]
34

That is the stairs problem, solved for every staircase up to 8, with no function at all. Position i of the list holds the number of ways to climb i stairs. Each new entry is made from the two before it, and by the time it is wanted they are already there.

From a memo to a table

Put the remembered function and the table side by side.

Nothing about the problem has changed. The question at each position is the same question, and the step is the same step. What has changed is who decides the order. With a memo, the calls work downward from the question you asked and the answers come back up. With a table, you start at the bottom and fill upward.

Two things follow at once. There are no calls waiting inside one another, so there is no limit on how long the chain may be: five thousand stairs, or five million, is a loop like any other. And the work is plain to see: the loop runs once for each cell, and each cell is a fixed number of steps.

The order of filling

A table is right only if every cell is filled after the cells it reads. For the stairs that is easy to arrange: each cell reads the two before it, so fill from left to right.

When it is not arranged, nothing fails. The loop reads a cell that still holds whatever it was created with, and carries on.

def ways_backwards(n):
    table = [0] * (n + 1)
    table[0] = 1
    table[1] = 1
    for stair in range(n, 1, -1):
        table[stair] = table[stair - 1] + table[stair - 2]
    return table

print(ways_backwards(5))

[1, 1, 2, 1, 0, 0]

Filling from the top down, stair 5 was made from stairs 4 and 3 before either had been worked out, when both still held 0. Stair 3 was made from stair 2, still 0, and stair 1: it came out as 1 where 3 is right. Only stair 2 came out right, because the cells it reads were filled before the loop.

So before writing the loop, ask of one cell: which cells does this one read? Then choose an order in which those always come first. If a cell reads the cells to its left, go left to right. If it reads cells further on, as in a function that looks forward from a position to the end, fill from the end backwards. The rule comes from the step. It is not a habit.

A table with two sides

When the key has two parts, the table has rows and columns. Routes on a grid of streets: the number of routes to a crossing is the routes to the crossing on its left plus the routes to the one above.

def route_table(across, down):
    table = []
    for row in range(down + 1):
        table.append([1] * (across + 1))
    for row in range(1, down + 1):
        for col in range(1, across + 1):
            table[row][col] = table[row][col - 1] + table[row - 1][col]
    return table

for line in route_table(3, 2):
    print(line)

[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]

The top row and the left column are the cases that stop: one route along a straight street. Every other cell reads its left neighbour and the cell above. Filling row by row, left to right, both are ready: the left neighbour was filled a moment ago, and the row above was finished before this row began.

Notice how the table is made: a new list for each row, inside a loop. [[1] * 4] * 3 would look the same when printed and would be one row repeated three times, as you saw in References and Grids. Filling one cell would then fill a whole column.

A table of this kind costs rows × columns steps and the same again in memory. That is the number of different questions, as before. It is worth working out before you start: two words of a thousand letters each make a table of a million cells.

Getting the choices back

So far every table has answered "how many?" or "how much?". Often you want more: not the largest total a singer can earn, but which nights she should sing.

The table already holds enough to work that out. Take the cheapest way up a staircase where each stair has a cost, climbing one or two at a time. best[i] is the least total cost of standing on stair i.

costs = [0, 4, 1, 5, 2, 6, 1]
best = [0, 4]
for stair in range(2, len(costs)):
    best.append(costs[stair] + min(best[stair - 1], best[stair - 2]))
print(best)

path = []
stair = len(costs) - 1
while stair > 0:
    path.append(stair)
    if stair == 1 or best[stair - 1] <= best[stair - 2]:
        stair = stair - 1
    else:
        stair = stair - 2
path.reverse()
print(path)

[0, 4, 1, 6, 3, 9, 4]
[2, 4, 6]

The first loop fills the table as before. The second walks back from the answer. At stair 6 the total is 4, made of the stair's own cost of 1 and the smaller of the totals at stairs 5 and 4. Stair 4 is smaller, at 3, so the climb came from stair 4. At stair 4 it came from stair 2, and from stair 2 it came from the ground. Reversed, that is the climb: stairs 2, 4 and 6, at a cost of 1 + 2 + 1.

The walk asks, at each cell, the same question the filling asked, and looks at which answer won. It takes one step for each choice made, so it adds almost nothing to the cost. What it needs is the whole table, kept until the end.

When two choices are equally good, the walk has to pick one, and which one it picks decides which of several equally good answers you get. Say which in a comment, and if a task asks for a particular one, that is where to arrange it.

Keeping only what is needed

The stairs table has n entries, and each new one is made from the last two. The rest are never looked at again. So two variables are enough.

def ways(n):
    before = 1
    last = 1
    for stair in range(2, n + 1):
        before, last = last, before + last
    return last

print(ways(8), ways(60))

34 2504730781961

last is the answer for the stair just done, and before the one before that. Each turn moves both along by one. The same works for a table with rows when each row reads only the row above: keep two rows, not all of them.

This saves memory, not steps, and it has a price. With only the last two entries there is nothing to walk back through. If you want the choices as well as the value, keep the table.

Memo or table?

Both give the same answers, and both are costed the same way: the number of questions answered, times the work for one. When they answer the same questions, the cost in steps is the same. They do not always answer the same questions, as the second row of the table shows. Choose between them by that, and by what else matters.

A memo is the better first draft: it is the function you can already check on small inputs, made fast. A table is what it usually becomes when the inputs grow, or when the choices are wanted. And when only a few of the possible questions are ever reached, the memo stays ahead, because a table fills the cells nobody asked about.

In the lab

You will build the stairs answers as a list, see a table filled in the wrong order, and find the cheapest climb up five thousand stairs. You will fill a table with two sides and use one to find what two words share. You will walk back through a table, and find which nights a singer should take. You will cut a table down to two variables, find the longest rising run in a list of heights, and compare a memo with a table on a problem where most of the table is wasted. Four assignments follow: the cheapest path across a grid, a table with two mistakes, the ways to pay an amount, and two equal piles.