Dynamic Programming: Memoization, Tabulation & Patterns

Q: Should I use memoization or tabulation?

Start with memoization (top-down): write the natural recursive solution, then add a cache — it's the most intuitive and only computes the subproblems you actually need. Switch to tabulation (bottom-up) when recursion depth could overflow the stack, when you want to avoid recursion overhead, or when you need to optimize space by collapsing the table. They have the same time complexity; the choice is about ergonomics and constraints, not correctness.

Dynamic Programming

Dynamic programming (DP) is a technique for solving problems that break into overlapping subproblems — where the same smaller problems are solved repeatedly. The insight is simple but powerful: compute each subproblem once, cache the result, and reuse it. This turns exponential brute-force recursion into efficient polynomial-time algorithms, often a dramatic speedup.

DP intimidates people more than it should. It's really just smart recursion with a cache (or its bottom-up equivalent). The hard part isn't the mechanics — it's recognizing that a problem has the right shape and defining the right subproblem. Once you see the pattern, the solution often writes itself.

TL;DR

DP solves problems with overlapping subproblems and optimal substructure.
Compute each subproblem once, cache it, reuse — turning exponential into polynomial.
Two styles: memoization (top-down recursion + cache) and tabulation (bottom-up table).
The skill is recognizing the subproblem, not the mechanics.

Quick Example

Naive Fibonacci recomputes the same values exponentially; memoization makes it linear:

When DP Applies

A problem is a DP candidate when it has both:

Overlapping subproblems — the same smaller problems recur (so caching helps). Without this, plain divide-and-conquer (like mergesort) suffices.
Optimal substructure — an optimal solution is built from optimal solutions to subproblems.

If subproblems don't repeat, DP buys you nothing. If the optimal solution can't be composed from optimal subsolutions, DP doesn't apply.

Memoization vs Tabulation

Recognizing DP Problems

Common signals: "find the minimum/maximum," "count the number of ways," "is it possible to...," with choices at each step and overlapping state. Classic examples:

Fibonacci / climbing stairs — count ways.
Knapsack — maximize value under a weight limit.
Longest common subsequence / edit distance — string alignment.
Coin change — fewest coins to make an amount.
Grid paths — count/optimize paths through a grid.

The recipe: define the state (what a subproblem represents), the recurrence (how a state builds from smaller ones), and the base cases.

Best Practices

Start with the recursive brute force, then add memoization — it's the easiest path to a correct DP.
Define the state precisely — what does dp[i] (or dp[i][j]) mean? Get this right and the recurrence follows.
Identify base cases explicitly.
Optimize space last — many 2D tables collapse to 1D once it works.
Don't force DP — if subproblems don't overlap, a simpler approach is better.

Common Mistakes

Exponential recursion without caching

A wrong or vague state definition

FAQ

How do I recognize a dynamic programming problem?

Look for two traits: the problem asks for an optimum or a count ("minimum cost," "maximum value," "number of ways," "is it possible"), and solving it involves making a sequence of choices where the same subproblems recur. If brute-force recursion would recompute the same states repeatedly (overlapping subproblems) and the optimal answer composes from optimal sub-answers (optimal substructure), it's a DP problem. With practice, the phrasing alone often gives it away.

Should I use memoization or tabulation?

Start with memoization (top-down): write the natural recursive solution, then add a cache — it's the most intuitive and only computes the subproblems you actually need. Switch to tabulation (bottom-up) when recursion depth could overflow the stack, when you want to avoid recursion overhead, or when you need to optimize space by collapsing the table. They have the same time complexity; the choice is about ergonomics and constraints, not correctness.

Why is dynamic programming faster than plain recursion?

Because naive recursion on an overlapping-subproblem problem recomputes the same values an exponential number of times — Fibonacci's tree recomputes fib(2) over and over. DP computes each distinct subproblem once and reuses the stored result, so total work drops to the number of distinct subproblems times the cost per transition — typically polynomial. It's the same algorithm structure; the cache is what eliminates the redundant exponential recomputation.

What's the difference between dynamic programming and divide-and-conquer?

Both break a problem into subproblems, but divide-and-conquer (like mergesort) splits into independent, non-overlapping subproblems — there's nothing to cache because each is solved once anyway. Dynamic programming applies specifically when subproblems overlap, so caching and reuse give a real speedup. If your subproblems don't repeat, you don't need DP — plain recursion or divide-and-conquer is simpler and just as fast.