Chapter 59: Tabulation
Tabulation is one of the two main ways to implement Dynamic Programming (the other being Memoization / Top-Down approach).
Let me explain it to you very clearly and slowly — like I’m teaching a friend who is just starting to understand DP and wants to really “get it” deeply, not just memorize the term.
1. What is Tabulation really? (very simple definition)
Tabulation = bottom-up dynamic programming
Instead of starting from the original (big) problem and breaking it down recursively (like in memoization), we start from the smallest possible subproblems and build up the solution step by step until we reach the original problem.
We use a table (usually an array or 2D array) to store the results of subproblems in a very systematic, iterative way.
Key points:
- No recursion → no recursion stack
- We fill the table in a specific order (usually from small to large)
- We never recompute the same subproblem
- The final answer is usually in the last cell of the table
2. Real-life analogy (very easy to remember)
Imagine you want to calculate how many ways you can climb a staircase of n steps (you can take 1 or 2 steps at a time).
Without tabulation (naive recursion):
You keep asking: “How many ways to reach step n?” → “ways(n-1) + ways(n-2)” → and this branches exponentially — very slow
With tabulation (bottom-up):
You start from the ground floor and work your way up:
- Step 0: 1 way (you’re already there)
- Step 1: 1 way (only 1 step)
- Step 2: 2 ways (1+1 or 2)
- Step 3: 3 ways (from step 1 + 1 step, or step 2 + 1 step)
- Step 4: 5 ways (from step 2 + 2 steps, or step 3 + 1 step)
You fill a table from bottom to top → when you reach step n, you already know the answer.
That’s tabulation: build the solution from the smallest problems upward.
3. Classic Example: Fibonacci with Tabulation
Problem: Find the nth Fibonacci number (Fib(0) = 0, Fib(1) = 1, Fib(n) = Fib(n-1) + Fib(n-2))
Naive recursive (very slow):
|
0 1 2 3 4 5 6 7 8 9 |
def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) |
Tabulation (bottom-up) — the proper way:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def fib(n): if n <= 1: return n # Create table (array) of size n+1 dp = [0] * (n + 1) # Base cases dp[0] = 0 dp[1] = 1 # Fill the table from bottom to top for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] |
What happens in memory:
n = 6
dp array:
index → 0 1 2 3 4 5 6 value → 0 1 1 2 3 5 8
You fill it from left to right — no repeated work.
Time Complexity: O(n) Space Complexity: O(n)
Even better space-optimized version (O(1) space):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b |
4. Another Classic Example: 0/1 Knapsack (very common interview problem)
Problem:
- n items
- Each item has weight wᵢ and value vᵢ
- Knapsack capacity = W
- Maximize value without exceeding weight
- You can take each item 0 or 1 time (no fractions)
Tabulation approach (bottom-up 2D DP)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def knapsack(weights, values, W, n): # dp[i][w] = max value using first i items with capacity w dp = [[0] * (W + 1) for _ in range(n + 1)] # Fill the table for i in range(1, n + 1): for w in range(1, W + 1): # Option 1: don't take item i no_take = dp[i-1][w] # Option 2: take item i (only if possible) take = 0 if weights[i-1] <= w: take = values[i-1] + dp[i-1][w - weights[i-1]] dp[i][w] = max(no_take, take) return dp[n][W] |
Table filling order:
- We start from smallest subproblems (few items, small capacity)
- Build up to the full problem (all items, full capacity)
- Each cell is computed only once
- Final answer is in dp[n][W]
Time Complexity: O(n × W) Space Complexity: O(n × W) (can be optimized to O(W))
5. Tabulation vs Memoization – Very Important Comparison
| Feature | Tabulation (Bottom-up) | Memoization (Top-down) |
|---|---|---|
| Approach | Iterative — fill table from small to large | Recursive + cache |
| Recursion stack | No | Yes — can cause stack overflow for deep recursion |
| Order of computation | Forced by loop order | Lazy — only compute needed subproblems |
| Space (typical) | O(n × W) (but optimizable) | O(n × W) + recursion stack |
| Easier to optimize space | Yes (often to O(W) or O(1)) | Harder |
| Code style | More like normal loops | Looks like natural recursion |
| Common in interviews | Very common (cleaner for many problems) | Also common |
| When to prefer | When table size is manageable, want iterative | When recursion is more natural |
Most competitive programmers and interviewers prefer tabulation because:
- No recursion depth issues
- Better cache performance
- Easier to optimize space
- Looks cleaner in code
6. Summary – Tabulation in one line each
- Tabulation = bottom-up dynamic programming
- Start from smallest subproblems and build up to the original problem
- Use a table (array/2D array) to store subproblem results
- Fill the table in a specific order (usually small → large)
- Never recompute the same subproblem
- Time complexity usually O(n × something) depending on problem
- Space usually O(n × something) but often optimizable to O(n) or O(1)
- Cleaner, safer, and more cache-friendly than memoization in many cases
- One of the two pillars of dynamic programming (the other is memoization)
Would you like to continue deeper?
Very common next topics people ask:
- Tabulation vs Memoization – detailed comparison with same problem
- How to do space optimization in tabulation (very common interview question)
- Tabulation on 0/1 Knapsack full example with table
- Tabulation on Fibonacci, LCS, Edit Distance (classic problems)
- Common mistakes when writing tabulation code
Just tell me which direction you want to go — I’ll explain it in the same calm, detailed, teacher style with lots of tables and examples 😊
