Introduction to Dynamic Programming
Overlapping subproblems and optimal substructure: turn exponential recursion into polynomial time by remembering answers (memoization).
On this page
Dynamic programming has a fearsome reputation, but the core idea is simple: don't solve the same subproblem twice. DP is just recursion plus memory. Once you can spot the two conditions that make it apply and add a cache, exponential solutions collapse to polynomial ones.
The two conditions
DP applies when a problem has both:
- Overlapping subproblems - the recursion solves the same smaller problems repeatedly.
- Optimal substructure - the optimal answer is built from optimal answers to subproblems.
Fibonacci is the canonical illustration of the waste (and the fix). Naive recursion recomputes the same values exponentially:
// naive: O(2^n) — fib(5) recomputes fib(3) twice, fib(2) three times, ...
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // massive recomputation
}Memoization: recursion with a cache
Memoization (top-down DP) keeps the natural recursion but remembers each subproblem's answer the first time it's computed, so repeats are instant lookups. One cache turns O(2^n) into O(n):
// memoized: O(n) — each fib(k) computed once
int fib(int n, Integer[] memo) {
if (n <= 1) return n;
if (memo[n] != null) return memo[n]; // already solved
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // solve once, store
}Tabulation: build the table bottom-up
Tabulation (bottom-up DP) flips the direction: instead of recursing down, iterate from the base cases up, filling a table where each entry uses earlier ones. No recursion, no stack:
// tabulated: O(n) time, O(1) space (only the last two values needed)
int fib(int n) {
if (n <= 1) return n;
int prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr; // each value from the two before it
prev = curr; curr = next;
}
return curr;
}Both give O(n); memoization is closer to the natural recursion (easier to derive), while tabulation avoids recursion overhead and often allows space optimization. Most DP solutions can be written either way - derive it recursively with memoization, then convert to a table if needed.
How to approach any DP
- Write the brute-force recursion (the 'try everything' solution). 2. Notice it recomputes subproblems.
- Add a cache keyed by the recursion's parameters - that's memoization, and usually enough. 4. Optionally convert to bottom-up tabulation for speed/space. The hard part is step 1: defining the state and the recurrence. The memoization is mechanical.
Imagine each tax form needs figures from several other forms, which need figures from still others - and many forms feed into multiple places. If you recompute a sub-form every time it's referenced, you redo enormous work. Instead you keep a folder of completed forms: the first time you finish one, you file it; every later reference just pulls the finished copy. That folder is memoization - each subproblem solved once and reused - turning a mountain of duplicated arithmetic into a single pass.
Consider counting the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. The recursion is ways(n) = ways(n-1) + ways(n-2). Explain why the naive recursion is exponential and how memoization makes it linear, and note what famous sequence this equals.
What two properties must a problem have for dynamic programming to apply?
Key takeaways
- Dynamic programming is recursion plus memory: solve each subproblem once and reuse the answer.
- It applies when a problem has overlapping subproblems and optimal substructure.
- Memoization (top-down) keeps the natural recursion but caches results, turning O(2^n) into O(n) for Fibonacci-like recurrences.
- Tabulation (bottom-up) fills a table from base cases upward, avoiding recursion and often enabling space savings.
- Approach: write the brute-force recursion, notice recomputation, add a cache keyed by the parameters - defining the state and recurrence is the hard part.