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.
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.
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.
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.