Pattern Reference
Recursion + Memoization
"Top-down DP, memoization patterns, recursion tree optimization, stack depth management, tabulation conversion."
Loading...
Deep Dive Tutorial
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
Converting brute-force recursion to memoized DP
// 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
lightbulb
Cache key = all parameters that affect the output.
If your function is
- 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).
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).
Worked Problems
brain
Memoization vs bottom-up DP:
- 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)
- 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)