Tabulation (Bottom-Up DP)
What you'll learn: How to build dynamic programming solutions by filling a table from the smallest subproblems up to your target answer.
The Core Idea
Tabulation is the iterative approach to dynamic programming. Instead of starting at the main problem and recursing downward (like memoization), you start at the smallest subproblems and work your way up to the final answer, storing results in a table (usually an array or matrix) as you go.
Think of it like building a skyscraper: you don't start at the top and work down—you lay the foundation first, then build floor by floor until you reach the penthouse. Each floor relies on the one below it being complete.
How It Works
- Initialize a table (array) to store solutions to subproblems
- Fill base cases (the "smallest" problems you know the answer to)
- Iterate through the table in order, computing each entry using previously computed values
- Return the final entry, which contains the answer to your original problem
Key Differences from Memoization
- No recursion: purely iterative loops
- Bottom-up order: you solve small problems first, then combine them
- No stack overhead: no risk of stack overflow
- Predictable space: you allocate the entire table upfront
Example Pattern (Conceptual)
For a 1D problem with n subproblems:
- Create table of size n+1
- Set table[0] = base_case
- Loop i from 1 to n, computing table[i] from previous entries
- Return table[n]
Key Takeaway: Tabulation solves DP problems iteratively by systematically filling a table from base cases up to the target, avoiding recursion entirely while guaranteeing you solve each subproblem exactly once in dependency order.