Tabulation computes dynamic programming states in an explicit order, usually from smaller states to larger states.
It is the bottom-up style of dynamic programming.
Core Idea
The algorithm creates a table, fills base cases, and then fills later entries using already-computed earlier entries.
The hard part is choosing an order where every dependency is available before it is needed.
Tabulation turns the recurrence into loops. Instead of asking recursively for smaller answers, the algorithm arranges to compute those smaller answers first.
Function Contract
fib(n) expects a non-negative integer and returns the nth Fibonacci number.
The table dp has one entry per state from 0 through n, and the loop fills entries in dependency order.
Python Example
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]The loop fills the table from small indexes to large indexes.
From Recurrence to Loop
For Fibonacci:
dp[i] = dp[i - 1] + dp[i - 2]The dependencies are smaller indexes, so the loop should go upward from 2 to n.
For a 2D grid where dp[r][c] depends on the top and left cells, a row-by-row loop works because top and left are already computed by the time the current cell is filled.
Why Use Tabulation
Tabulation can avoid recursion limits and make memory layout explicit. It also makes it easier to optimize memory when only recent table entries are needed.
The tradeoff is that tabulation may require more work to find the correct fill order.
Complexity
For the Fibonacci example, the table has n + 1 entries and each entry is filled once, so the time and space are O(n).
In general, tabulation cost comes from the table size and the work needed to fill each entry. A table with n * m entries and constant work per entry costs O(n * m).
Debugging Tip
When a tabulation solution is wrong, print a small table and compare it with the state definition. Each cell should answer the sentence assigned to that state.
Most tabulation bugs come from wrong base cases, wrong loop order, or reading a dependency before it has been computed.
Common Confusions
Tabulation is not always better than memoization. It can compute states that the top-down version would never need.
The table shape should follow the state. A one-dimensional state may need a list. A two-dimensional state may need a grid.
Another mistake is filling the table in an order that uses values before they are computed. The loop order must respect the recurrence dependencies.
When To Use It
Use tabulation when the dependency order is clear, recursion depth is a concern, or an iterative solution is easier to control.
If the top-down recurrence is clear but the bottom-up order is not, start with memoization and convert later if needed.
The Main Point
Tabulation turns a recurrence into loops. The loop order is correct only when every dependency has already been computed.