Tabulation (Bottom-Up)

Tabulation is bottom-up DP. Instead of asking recursively for the answer and letting calls discover dependencies, you allocate a table, initialize known base states, and fill remaining states in a deliberate order.

The table may be an array, a matrix, or a few variables. The important point is dependency order. When computing dp[i], every state referenced by its transition must already be available.

For one-dimensional prefix DP, order is usually left to right: dp[i] depends on earlier indices. For suffix DP, it may be right to left. For two-string DP like Edit Distance, row and column order works because each cell depends on its top, left, and diagonal neighbors. For interval DP, increasing interval length is common because shorter intervals must be solved before longer ones.

If you cannot find an order, draw arrows from each state to the states it depends on. A valid tabulation order is any topological order of that dependency graph.

Bottom-up code avoids stack overflow, often has better constant factors, and makes space optimization easier. It also forces you to state base cases precisely because the table starts from them. For classic problems like Climbing Stairs, House Robber, Unique Paths, and Coin Change, a bottom-up answer is usually the expected final form.

The downside is that bottom-up can be less obvious for irregular state spaces. It may compute states that are theoretically valid but never needed by the original query.

Before writing loops, know four things: the table dimensions, the meaning of each cell, the base cells, and the dependency direction. Then write loops that move from known states to unknown states.

A common mistake is copying a recurrence into a loop without checking whether referenced cells are already initialized. Another is using default zero values for states that should represent impossible or infinite answers.