DSA TrainerMemoization vs Tabulation: top-down or bottom-up dynamic programming?
Both of these are dynamic programming. They store subproblem answers so you never recompute them. People use the words interchangeably, then get told to 'just use DP' with no hint about which form to write. They solve the same problems in opposite directions.
The short answer
Same DP, opposite directions. Memoization is top-down: write the natural recursion, then cache results so a subproblem is never solved twice. Tabulation is bottom-up: fill a table starting from the smallest subproblems up to the answer, with no recursion at all.
The one question that settles it
Ask yourself: is it easier to describe the answer in terms of smaller answers, or to build up from the base cases? Write whichever you can express first. They give the same time complexity.
Reach for Memoization (Top-Down) when…
- ✓You can already see the recursive relationship and writing the recursion feels natural
- ✓Only some subproblems are actually reached, so you'd rather not compute the whole table
- ✓The state is awkward to order (string indices, several changing parameters at once)
- ✓You're upgrading a brute-force recursion you already wrote, so you add a cache and you're done
Reach for Tabulation (Bottom-Up DP) when…
- ✓The subproblems have an obvious order (0, 1, 2, … n) you can just loop over
- ✓You want to avoid recursion depth limits and call-stack overhead
- ✓You suspect you can drop the table down to a couple of rolling variables and save space
- ✓Every subproblem gets used, so filling the whole table wastes nothing
Side by side
| Memoization (Top-Down) | Tabulation (Bottom-Up DP) | |
|---|---|---|
| Direction | Top-down: answer → subproblems | Bottom-up: subproblems → answer |
| Uses recursion? | Yes, plus a cache | No, loops fill a table |
| What it computes | Only the subproblems it actually needs | Every subproblem, in order |
| Main risk | Stack overflow on very deep recursion | Wasted work if many states go unused |
| Space tricks | A cache (hash map or array) | Often reducible to O(1)–O(n) rolling variables |
| Easiest when | You already wrote the recursion | The fill order is obvious |
Practice each one
Guided hints, not spoilers. Feel the difference on real problems.
Memoization (Top-Down)
Tabulation (Bottom-Up DP)
Frequently asked questions
- Are memoization and dynamic programming the same thing?
- Memoization is one way to do DP (top-down). Tabulation is the other (bottom-up). 'Dynamic programming' is the umbrella term for both. The core idea is storing subproblem answers to avoid recomputing them. So every memoized solution is DP, but DP isn't only memoization.
- Which one is faster?
- They share the same time complexity. Tabulation usually has a smaller constant factor (no recursion overhead) and makes space optimization easier. Memoization can come out ahead when many subproblems are never actually needed, since it only computes the ones it reaches.
- Which should I learn first as a beginner?
- Memoization. It's the smaller leap: write the brute-force recursion you'd write anyway, then add a cache so repeated calls return instantly. Tabulation asks you to work out the correct fill order up front, a harder skill that's easier to learn once memoization has made the recurrence obvious.
Stop guessing which pattern to use
The whole point of DSA Trainer: learn to recognize the pattern before you write a line of code. Guided hints, not answers.