Pattern Guide
Recursion & Memoization
"Top-down DP. Cache the result of each subproblem. Never recompute."
Memoization converts exponential recursion to polynomial DP by caching results. It's "top-down DP" — write the recursive solution first, then add a cache. Learn when memoization is applicable, how to choose the cache key, handle cycles, and when to prefer bottom-up DP instead.
Problems you can solve with this pattern
5 problems · click any to start solving
// STEP 1: Write brute-force recursion
function fibSlow(n) {
if (n <= 1) return n;
return fibSlow(n-1) + fibSlow(n-2); // O(2^n)
}
// STEP 2: Add a memo map (or object)
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // cache hit
const result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
memo.set(n, result); // cache miss: compute and store
return result;
}
// Now O(n) — each unique n computed exactly once
// STEP 3 (optional): Convert to bottom-up DP
function fibDP(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
return curr;
}
// Top-down (memoization): natural recursion order, only compute needed subproblems
// Bottom-up (tabulation): explicit fill order, typically slightly faster (no call stack)Memoization is the simplest way to add DP to a recursive solution. Write the brute-force recursion first, identify what arguments uniquely determine the output, use those as the cache key, and add a lookup at the start. The only requirement: the function must be pure (no side effects — same inputs always produce same output).
The Memoization Template
// STEP 1: Write brute-force recursion
function fibSlow(n) {
if (n <= 1) return n;
return fibSlow(n-1) + fibSlow(n-2); // O(2^n)
}
// STEP 2: Add a memo map (or object)
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // cache hit
const result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
memo.set(n, result); // cache miss: compute and store
return result;
}
// Now O(n) — each unique n computed exactly once
// STEP 3 (optional): Convert to bottom-up DP
function fibDP(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
return curr;
}
// Top-down (memoization): natural recursion order, only compute needed subproblems
// Bottom-up (tabulation): explicit fill order, typically slightly faster (no call stack)Choosing the Cache Key
If your function is
dfs(node, remaining, visited):- node + remaining → key (if visited can be derived)
- node + remaining + JSON.stringify(visited) → key (if visited must be tracked)
Warning: Large or complex keys make caching slow. For bitmask states, the mask IS the key. For string states, stringify carefully.
The cache key determines complexity: O(unique states × work per state).
- Memoization (top-down): write recursion first, add cache. Natural order. Only computes needed subproblems. Easy to implement. Risk: stack overflow for large n.
- Bottom-up (tabulation): fill DP table iteratively. No stack overflow. Often faster (no function call overhead). Requires knowing fill order.
When memoization is preferred:
- Complex dependency order (interval DP, graph DP)
- Only a subset of states are needed
- Problem naturally expresses as "from state A, what's the best?"
When bottom-up is preferred:
- All states needed (full table)
- Simple 1D/2D fill order
- n is very large (stack overflow risk)