Bottom-up order of execution

In the previous lesson we looked at top-down order of execution using recursion and a memoised cache. It is the strategy that lets the recursion itself discover the dependency order, computing each state lazily the first time it is requested and caching the result.

In this lesson we will learn about the other natural way to satisfy the same dependency constraint, bottom-up iterative order of execution. Instead of letting the recursion discover the order at runtime, the programmer commits to an explicit iteration order in advance. The base cases are filled in first, and then a loop visits each remaining state in an order that guarantees its dependencies are already computed by the time it is reached. It executes the same recurrence, has the same base cases and the same final values, but a completely different control flow.

What bottom-up code looks like

A bottom-up dynamic programming algorithm has a very simple template. We allocate a table indexed by states and fill in the base cases directly. We then loop through the remaining states in an iteration order that respects the dependency structure and at each cell, we apply the recurrence, reading the values of dependencies (which by construction are already filled in) and writing the resulting value. At the end, we read the answer from the target cell.

What changes from problem to problem is the shape of the table, the set of base cases, and crucially, the iteration order. Everything else is just an instantiation of the recurrence we have already derived.