Tabulation (bottom-up)
Overview
Tabulation builds the DP table iteratively from the base cases UP to the final answer, in an order that guarantees every cell's dependencies are already filled when you reach it.
It avoids recursion-call overhead and stack-depth limits (no risk of stack overflow). It is also generally easier to trace on paper and space-optimize.
Where used: Dynamic Programming, High-performance systems where stack depth is a concern
Why learn this
- While top-down is often easier to write, bottom-up is immune to stack overflow issues.
- Tabulation is a prerequisite for space optimization (collapsing a 2D table into a 1D array).
Common mistakes
- Filling the table in the wrong order: If you read a cell before its dependency is filled, you get garbage values. You must iterate in topological order of the dependencies.
- Assuming bottom-up is ALWAYS faster than top-down: They have the same asymptotic time complexity. However, tabulation computes EVERY state in the table, even unreachable ones, whereas top-down only computes what it needs.
Recall questions
- What is the main advantage of bottom-up tabulation over top-down memoization?
- What is a disadvantage of bottom-up tabulation compared to top-down?
Understanding checks
What happens if you fill a 2D DP table row by row from top to bottom, but the transition for `dp[r][c]` depends on `dp[r+1][c]`?
You will read empty/uninitialized values because the dependency (`r+1`) hasn't been computed yet.
Tabulation requires filling in topological order. If it depends on `r+1`, you must iterate the rows backwards (from bottom to top).
If your graph of subproblems is very sparse (only a few states are actually visited), which approach is generally better: top-down or bottom-up?
Top-down memoization.
Top-down only computes the states it actually visits. Bottom-up typically iterates over the entire domain and computes every possible state, wasting time on unreachable ones.
Practice tasks
Convert to bottom-up
Convert this top-down Fibonacci function into a bottom-up tabulated version using an array.
Challenge
Correct Iteration Order
Suppose your DP state depends on `dp[i+1][j]` and `dp[i][j-1]`. In what order should you iterate the rows `i` and columns `j`?
Continue learning
Previous: Memoization (top-down)
Next: Space optimization