Memoization
What Is Memoization?
Memoization is the top-down approach to DP: write the natural recursive solution first, then add a cache to store results for states that have already been computed.
THE PATTERN — three lines transform naive recursion into DP:
NAIVE RECURSION: MEMOIZED:
function solve(state): function solve(state):
if base_case: return base if base_case: return base
if cache[state] != UNSET: ← CHECK
return cache[state]
result = f(solve(sub1), result = f(solve(sub1),
solve(sub2)) solve(sub2))
return result cache[state] = result ← STORE
return cache[state]
Three changes:
1. Declare a cache (array or HashMap)
2. Check cache at the top (after base cases)
3. Store result before returning
Everything else stays IDENTICAL to the naive recursive solution.
The Correct Order of Operations
ALWAYS in this order:
function solve(state):
① BASE CASES FIRST
if state is trivially solvable: return answer
② CACHE CHECK SECOND
if cache[state] is set: return cache[state]
③ COMPUTE RECURSIVELY
result = combine(solve(sub1), solve(sub2), ...)
④ STORE BEFORE RETURNING
cache[state] = result
return result
WRONG ORDER (common bug):
function solve(state):
if cache[state] != -1: return cache[state] ← check BEFORE base cases
if base_case: return base ← base case AFTER check
...
Problem: cache[base_state] = -1 initially → falls through to recursive call
on a state that should return directly → may access invalid indices.
Step-by-Step Conversion: Fibonacci
Converting naive recursion to memoized step by step.
STEP 1 — NAIVE RECURSION (exponential):
fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
STEP 2 — ADD MEMO ARRAY:
memo = [-1] * (n+1) ← sentinel -1 = "not computed yet"
STEP 3 — ADD CACHE CHECK after base cases:
fib(n, memo):
if n <= 1: return n ← base case first
if memo[n] != -1: return memo[n] ← cache check second
STEP 4 — COMPUTE AND STORE:
fib(n, memo):
if n <= 1: return n
if memo[n] != -1: return memo[n]
memo[n] = fib(n-1, memo) + fib(n-2, memo) ← compute+store
return memo[n]
Call stack for fib(5) WITH memoization:
fib(5) → fib(4) → fib(3) → fib(2) → fib(1)=1 ← base
→ fib(0)=0 ← base
memo[2]=1 ← stored
→ fib(1)=1 ← base
memo[3]=2 ← stored
→ fib(2)=1 ← memo hit! (not recomputed)
memo[4]=3 ← stored
→ fib(3)=2 ← memo hit!
memo[5]=5
Total calls: 9 (not 15 like naive)
Each unique state computed exactly once.
Memo Data Structures
OPTION 1 — Array (fastest, fixed size):
int[] memo = new int[n+1]; // 1D
int[][] memo = new int[m][n]; // 2D
Arrays.fill(memo, -1); // initialise sentinel
Pros: O(1) access, cache-friendly, minimal overhead
Cons: Must know max state range upfront; wastes space for sparse problems
OPTION 2 — HashMap (flexible, any key type):
Map<Integer, Integer> memo = new HashMap<>();
Map<String, Integer> memo = new HashMap<>();
Map<List<Integer>, ...> — use tuple/string as key for multi-dim state
Pros: No range needed; no sentinel needed (containsKey() check);
handles arbitrary key types
Cons: Higher constant factor; boxing overhead for primitives; less cache-friendly
OPTION 3 — Language built-ins:
Python: @functools.lru_cache(maxsize=None) ← one decorator, done
@functools.cache ← Python 3.9+, same thing
Java: No built-in; use HashMap or array
C++: No built-in; use unordered_map or array
JS: Closures + Map (manual)
CHOOSING:
State fits in bounded array (indices < 10^4) → ARRAY
State is sparse / unbounded / non-integer → HASHMAP
Python and quick to implement → @lru_cache
Complete Memoization Examples
1import java.util.*;
2
3public class MemoizationExamples {
4
5 // ── 1. Fibonacci — 1D memo ─────────────────────────────────────────
6 public static long fib(int n, long[] memo) {
7 if (n <= 1) return n; // ① Base cases
8 if (memo[n] != -1) return memo[n]; // ② Cache check
9 memo[n] = fib(n-1, memo) + fib(n-2, memo); // ③ Compute
10 return memo[n]; // ④ Return stored
11 }
12
13 // ── 2. Grid Unique Paths — 2D memo ────────────────────────────────
14 // dp[i][j] = number of paths to cell (i,j)
15 public static int uniquePaths(int i, int j, int[][] memo) {
16 if (i == 0 || j == 0) return 1; // ① Base: edges = 1 path
17 if (memo[i][j] != -1) return memo[i][j]; // ② Cache check
18 memo[i][j] = uniquePaths(i-1, j, memo)
19 + uniquePaths(i, j-1, memo); // ③ Compute
20 return memo[i][j]; // ④ Return
21 }
22
23 // ── 3. Coin Change — 1D memo ──────────────────────────────────────
24 // dp[amount] = min coins to make this amount
25 public static int coinChange(int amount, int[] coins, int[] memo) {
26 if (amount == 0) return 0; // ① Base: 0 coins for 0
27 if (amount < 0) return Integer.MAX_VALUE; // ① Base: impossible
28 if (memo[amount] != -1) return memo[amount]; // ② Cache check
29
30 int best = Integer.MAX_VALUE;
31 for (int coin : coins) {
32 int sub = coinChange(amount - coin, coins, memo);
33 if (sub != Integer.MAX_VALUE) {
34 best = Math.min(best, 1 + sub);
35 }
36 }
37 memo[amount] = best; // ③+④ Store and return
38 return memo[amount];
39 }
40
41 // ── 4. Longest Common Subsequence — 2D memo ───────────────────────
42 // dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
43 public static int lcs(String s1, String s2, int i, int j, int[][] memo) {
44 if (i == 0 || j == 0) return 0; // ① Base: empty string
45 if (memo[i][j] != -1) return memo[i][j]; // ② Cache check
46
47 if (s1.charAt(i-1) == s2.charAt(j-1)) {
48 memo[i][j] = 1 + lcs(s1, s2, i-1, j-1, memo); // Match: extend
49 } else {
50 memo[i][j] = Math.max(
51 lcs(s1, s2, i-1, j, memo), // Skip char from s1
52 lcs(s1, s2, i, j-1, memo) // Skip char from s2
53 );
54 }
55 return memo[i][j];
56 }
57
58 // ── 5. Word Break — HashMap memo ──────────────────────────────────
59 // Can s[start..] be segmented using words from dict?
60 public static boolean wordBreak(String s, int start,
61 Set<String> dict,
62 Map<Integer, Boolean> memo) {
63 if (start == s.length()) return true; // ① Base: reached end
64 if (memo.containsKey(start)) return memo.get(start); // ② Cache
65
66 for (int end = start + 1; end <= s.length(); end++) {
67 String word = s.substring(start, end);
68 if (dict.contains(word) && wordBreak(s, end, dict, memo)) {
69 memo.put(start, true);
70 return true;
71 }
72 }
73 memo.put(start, false);
74 return false;
75 }
76
77 public static void main(String[] args) {
78 // Fibonacci
79 long[] fibMemo = new long[51];
80 Arrays.fill(fibMemo, -1);
81 System.out.println("fib(10): " + fib(10, fibMemo)); // 55
82
83 // Unique Paths (3×3 grid)
84 int[][] pathMemo = new int[3][3];
85 for (int[] row : pathMemo) Arrays.fill(row, -1);
86 System.out.println("paths(2,2): " + uniquePaths(2, 2, pathMemo)); // 6
87
88 // Coin Change
89 int[] coinMemo = new int[7];
90 Arrays.fill(coinMemo, -1);
91 System.out.println("coins(6,[1,3,4]): " +
92 coinChange(6, new int[]{1,3,4}, coinMemo)); // 2
93
94 // LCS
95 String s1 = "abcde", s2 = "ace";
96 int[][] lcsMemo = new int[s1.length()+1][s2.length()+1];
97 for (int[] row : lcsMemo) Arrays.fill(row, -1);
98 System.out.println("LCS: " + lcs(s1, s2, s1.length(), s2.length(), lcsMemo)); // 3
99
100 // Word Break
101 Set<String> dict = new HashSet<>(Arrays.asList("leet", "code", "lee", "t"));
102 Map<Integer, Boolean> wbMemo = new HashMap<>();
103 System.out.println("wordBreak: " + wordBreak("leetcode", 0, dict, wbMemo)); // true
104 }
105}Output:
fib(10): 55
unique_paths(2,2): 6
coin_change(6): 2
LCS(abcde, ace): 3
word_break: true
Dry Run: Memoized Coin Change
coinChange(6, [1,3,4], memo={})
Call stack (top-down):
coinChange(6):
try coin=1: coinChange(5)
try coin=1: coinChange(4)
try coin=1: coinChange(3)
try coin=1: coinChange(2)
try coin=1: coinChange(1)
try coin=1: coinChange(0) → 0 ← base case
memo[1] = min(∞, 1+0) = 1; return 1
memo[2] = min(∞, 1+1) = 2; return 2
try coin=3: coinChange(0) → 0
memo[3] = min(2, 1+1, 1+0) = 1 (using coin 3); return 1
try coin=3: coinChange(1) → memo HIT! return 1
try coin=4: coinChange(0) → 0
memo[4] = min(∞, 1+1, 1+1, 1+0) = 1 (using coin 4); return 1
try coin=3: coinChange(2) → memo HIT! return 2
try coin=4: coinChange(1) → memo HIT! return 1
memo[5] = min(1+1, 1+2, 1+1) = 2; return 2
try coin=3: coinChange(3) → memo HIT! return 1
try coin=4: coinChange(2) → memo HIT! return 2
memo[6] = min(1+2, 1+1, 1+2) = 2; return 2
Final: coinChange(6) = 2 (use coins 3+3)
Memo hits avoided recomputing: coinChange(1), coinChange(2), coinChange(3) multiple times
Handling Multi-Dimensional State
PROBLEM: State has multiple dimensions — e.g., (index, remaining_capacity).
APPROACH 1 — Multi-dimensional array:
int[][] memo = new int[n+1][W+1];
fill with -1
Access: memo[i][w]
APPROACH 2 — HashMap with tuple key:
Map<String, Integer> memo = new HashMap<>();
Key: i + "," + w
Access: memo.get(i + "," + w)
APPROACH 3 — Python @lru_cache (automatic):
@lru_cache(maxsize=None)
def dp(i, w):
... # (i, w) is automatically the cache key
TRADEOFF:
Array: Faster O(1) access; requires knowing max bounds upfront
HashMap: Flexible; slightly slower; no bounds needed
lru_cache: Zero boilerplate; Python only; args must be hashable
EXAMPLE — 0/1 Knapsack:
State: (item_index, remaining_weight)
memo[i][w] = max value using items[0..i] with w capacity
def knapsack(i, w, weights, values, memo):
if i < 0 or w == 0: return 0 # ① Base
if memo[i][w] != -1: return memo[i][w] # ② Cache
skip = knapsack(i-1, w, weights, values, memo)
take = 0
if weights[i] <= w:
take = values[i] + knapsack(i-1, w-weights[i], weights, values, memo)
memo[i][w] = max(skip, take) # ③+④
return memo[i][w]
The Memo Initialization Checklist
CHOOSE THE RIGHT SENTINEL:
Answer type Sentinel value Reason
─────────────────────────────────────────────────────────────
Non-negative int -1 -1 can't be a valid answer
Any int (incl. neg) INT_MIN or flag array Needs separate "computed?" check
Counting (≥ 0) -1 Works fine
Minimum cost INT_MAX/2 or amount+1 Avoid overflow in 1 + dp[...]
Maximum value -1 Works for non-negative values
Boolean null / None Three-valued: true/false/unknown
BAD SENTINEL EXAMPLES:
Using 0 when 0 is a valid answer → false cache hits
Using INT_MAX for minimum cost → 1 + INT_MAX overflows to negative
Using -1 when answers can be -1 → treats valid -1 as "not computed"
SAFE PATTERNS:
Java: int[] memo = new int[n]; Arrays.fill(memo, -1);
Python: dict memo = {}; check `if n in memo`
Python: @lru_cache — no sentinel needed; None = not computed
C++: vector<int> memo(n, -1);
JS: const memo = {}; check `if (key in memo)`
Memoization vs Tabulation Preview
SAME PROBLEM — Fibonacci:
MEMOIZED (top-down): TABULATED (bottom-up):
fib(5) dp = [0, 1, 0, 0, 0, 0]
fib(4) dp[2] = dp[1]+dp[0] = 1
fib(3) dp[3] = dp[2]+dp[1] = 2
fib(2) dp[4] = dp[3]+dp[2] = 3
fib(1) → 1 dp[5] = dp[4]+dp[3] = 5
fib(0) → 0
memo[2] = 1 No recursion. Fill forward.
...
memo[3] = 2
memo[4] = 3
memo[5] = 5
Both give the same answer. Key differences:
Memoization: Computes only reachable states (lazy)
Natural recursive structure
Recursion overhead (~function call stack)
Tabulation: Computes ALL states in range (eager)
Iterative — no recursion overhead
Better cache locality (sequential memory access)
Full comparison in the next topic: Memoization vs Tabulation.
Complexity Analysis
MEMOIZED SOLUTION: Time = O(unique sub-problems × work per sub-problem) Space = O(unique sub-problems) for memo + O(depth) for call stack FIBONACCI: Sub-problems: n+1 unique states (fib(0)..fib(n)) Work per sub-problem: O(1) Time: O(n) Space: O(n) memo + O(n) call stack = O(n) UNIQUE PATHS (m×n grid): Sub-problems: m×n states Work per sub-problem: O(1) Time: O(m×n) Space: O(m×n) memo + O(m+n) call stack = O(m×n) COIN CHANGE (amount A, k coins): Sub-problems: A states (amount 0..A) Work per sub-problem: O(k) — try each coin Time: O(A×k) Space: O(A) memo + O(A) call stack = O(A) LCS (strings of length m and n): Sub-problems: m×n states Work per sub-problem: O(1) Time: O(m×n) Space: O(m×n) memo + O(m+n) call stack = O(m×n) CALL STACK DEPTH: For deeply recursive problems (n > 10,000), call stack may overflow. Python default limit: 1,000 calls. Increase: sys.setrecursionlimit(10000) Or convert to tabulation to eliminate recursion entirely.
Common Mistakes
Cache check before base cases. If memo[n] != -1 is checked before if n <= 0: return 0, the first call to a base-case state (which has memo[0]=-1 initially) falls through to the recursive call and accesses invalid indices. Always check base cases first, then cache.
Using 0 as a sentinel when 0 is a valid answer. In counting problems (number of ways = 0 is valid), using memo[state] = 0 as "not computed" causes incorrect early returns. Use -1 for non-negative answers, or a HashMap where key not in memo is the "not computed" check.
Passing mutable arguments to @lru_cache. Python's @lru_cache requires hashable arguments. Passing a list arr fails with TypeError: unhashable type: 'list'. Convert to tuple: tuple(arr), or pass indices instead of the array itself, or pass the array as a global/closure variable.
Not accounting for the call stack in space complexity. Memoization says "O(n) space for memo" but the call stack also uses O(depth) space. For fib(10000), the call stack depth is 10000 frames — potentially causing stack overflow. The actual space is O(n) memo + O(n) stack = O(n), but the stack has a hard system limit.
Reusing the memo table across different inputs. If you call coinChange([1,3,4], 6) and then coinChange([1,2,5], 8) using the same memo array, the cached results from the first call corrupt the second. Always create a fresh memo for each independent problem instance, or make coins part of the state key.
Interview Questions
Q: What are the two exact changes you make to convert naive recursion to memoization?
Add a cache (array or map). Add exactly two lines: (1) before computing, check the cache — if the current state is stored, return it immediately; (2) after computing, store the result in the cache before returning. The recursive structure, base cases, and recurrence all remain identical. These two changes transform exponential recursive calls into a polynomial number of unique computations.
Q: When should you use a HashMap instead of an array for the memo table?
Use a HashMap when: the state is non-integer or compound (e.g., pair of strings), the state range is too large or unbounded to allocate an array (e.g., states up to 10^9), or when most states in the range are never reached (sparse reachable sub-problems). Use an array when: the state is a bounded integer index (< 10^5 typically), O(1) array access matters, and most states are reachable. In Python, @lru_cache handles both cases automatically.
Q: Why might memoization be slower than tabulation in practice even though both are O(same)?
Three reasons: (1) Recursion overhead — each function call pushes a stack frame; tabulation's loop has none. (2) Cache locality — tabulation fills a contiguous array sequentially (CPU cache-friendly); memoization's HashMap has pointer indirection and random access patterns. (3) HashMap overhead — for non-array memo, each lookup involves hashing and collision handling. For large inputs, tabulation typically runs 2-10× faster than memoized recursion.
Summary
Memoization is top-down DP: write the natural recursive solution, then add a cache with two lines.
The three-line transformation:
- ›Declare a cache (array or HashMap), initialised to a sentinel value
- ›After base cases: check cache — if hit, return immediately
- ›Before returning: store the computed result in the cache
The correct order in every memoized function:
- ›Base cases (return directly, no cache needed)
- ›Cache check (return if already computed)
- ›Compute recursively
- ›Store and return
Five problems demonstrated:
- ›Fibonacci — 1D array memo
- ›Unique Paths — 2D array memo
- ›Coin Change — 1D array with careful sentinel (avoid overflow)
- ›LCS — 2D array with string indices
- ›Word Break — HashMap memo with integer index key
Sentinel guide:
- ›Non-negative answers → use -1
- ›Any-sign answers → use HashMap (no sentinel needed)
- ›Minimum cost → use
amount+1orINF/2(notINT_MAX— overflows) - ›Python → use
@lru_cache(zero boilerplate)
In the next topic you will explore Tabulation — the bottom-up DP approach, filling tables iteratively, determining fill order, and converting memoized solutions to tabulated ones.
What is the exact process memoization adds to a naive recursive function?