💾 Memoization

The Sticky Notes Analogy

Imagine calculating complex math problems repeatedly:

Without memoization: "What's 47 × 23?" → Calculate → 1081 "What's 47 × 23?" → Calculate again → 1081 "What's 47 × 23?" → Calculate again → 1081

Same work, three times!

With memoization: "What's 47 × 23?" → Calculate → 1081, write on sticky note "What's 47 × 23?" → Check sticky note → 1081 (instant!) "What's 47 × 23?" → Check sticky note → 1081 (instant!)

Memoization is keeping sticky notes for calculations you've already done.

Why Memoization Matters

The Fibonacci Disaster

Computing Fibonacci without memoization:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← calculated
│   │   └── fib(1)
│   └── fib(2) ← calculated AGAIN!
└── fib(3) ← calculated AGAIN!
    ├── fib(2) ← calculated AGAIN!
    └── fib(1)

fib(2) gets calculated MULTIPLE TIMES!

For fib(50): billions of redundant calculations!

With Memoization

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) → calculate, store: 1
│   │   └── fib(1) → 1
│   │   Return: 2, store
│   └── fib(2) → lookup! Already stored: 1
│   Return: 3, store
└── fib(3) → lookup! Already stored: 2
Return: 5

Each value calculated ONCE. Total: 5 calculations instead of 15!

Speedup: Exponential O(2^n) → Linear O(n)

How Memoization Works

The Pattern

1. Check: Have I solved this before?
   - Yes → Return stored answer
   - No  → Continue

2. Compute the answer

3. Store the answer for future use

4. Return the answer

What Gets Stored?

A mapping from input → output:

Memo dictionary:
  fib(0) → 0
  fib(1) → 1
  fib(2) → 1
  fib(3) → 2
  fib(4) → 3
  fib(5) → 5

The "key" is the function's input. The "value" is the result.

Memoization vs Dynamic Programming

They're closely related!

Same Problem, Different Approaches

Fibonacci n=5:

Memoization (top-down):
  fib(5) → needs fib(4), fib(3)
  fib(4) → needs fib(3), fib(2)
  ...cache as we go

Tabulation (bottom-up):
  dp[0] = 0
  dp[1] = 1
  dp[2] = dp[0] + dp[1] = 1
  dp[3] = dp[1] + dp[2] = 2
  dp[4] = dp[2] + dp[3] = 3
  dp[5] = dp[3] + dp[4] = 5

Both avoid redundant work. Choose based on preference!

When to Use Memoization

Good Candidates

1. Overlapping subproblems - Same inputs recur
2. Pure functions - Same input gives the same output (no hidden state)
3. Expensive computations - Worth the storage cost

Good candidates:
✓ Fibonacci, factorial
✓ Path counting in grids
✓ String matching (edit distance)
✓ Parsing (grammar rules)

Bad candidates:
✗ Functions with side effects
✗ Functions using random/time
✗ Functions with mutable inputs

Recognizing the Pattern

If you see:
- Recursive function
- Same calls happening multiple times
- Function depends on its inputs (not external state)

→ Add memoization!

Common Memoized Problems

1. Climbing Stairs

How many ways to climb n stairs (1 or 2 steps at a time)?

ways(n) = ways(n-1) + ways(n-2)

Without memo: O(2^n)
With memo: O(n)

Memo stores: {0:1, 1:1, 2:2, 3:3, 4:5, 5:8, ...}

2. Coin Change

Minimum coins to make amount?

minCoins(amount) = 1 + min(minCoins(amount - coin) for each coin)

Without memo: Exponential
With memo: O(amount × numCoins)

3. Longest Common Subsequence

Length of longest subsequence common to two strings?

lcs(i, j) =
  if s1[i] == s2[j]: 1 + lcs(i+1, j+1)
  else: max(lcs(i+1, j), lcs(i, j+1))

Memo key: (i, j) pair
Memo value: length

4. Edit Distance

Minimum edits to transform one string to another?

Subproblems: edit(i, j) for all prefix pairs
Memo: 2D table indexed by (i, j)

Implementation Tips

Choose the Right Key

The memo key should uniquely identify the subproblem:

Single argument: memo[n]
Multiple arguments: memo[(i, j)] or memo[i][j]
Complex state: memo[tuple(sorted(items))]

Consider Space Optimization

Sometimes you might need just the last few entries:

Fibonacci: Often you just need dp[n-1] and dp[n-2]
  → Use two variables instead of array
  → O(n) space → O(1) space!

Watch for Mutable Keys

Lists can't be dictionary keys. Convert to tuples!

Common Mistakes

1. Forgetting Base Cases

Usually handle the smallest subproblems first.

2. Wrong Cache Key

Wrong: memo[i] for problem with two changing variables
Right: memo[(i, j)] or memo[i][j]

3. Not Checking Cache First

Wrong: compute, then check cache
Right: check cache, then compute if needed

4. Caching Non-Pure Functions

Functions with side effects or randomness shouldn't be memoized!

FAQ

Q: When is memoization better than tabulation?

When you don't need all subproblems. Memoization often computes just what's needed.

Q: Does memoization usually help?

No! If there are no overlapping subproblems, memoization adds overhead without benefit.

Q: How much memory does memoization use?

O(number of unique subproblems). For Fibonacci(n), that's O(n).

Q: Can I use memoization with loops?

Memoization is typically used with recursion. For loops, use tabulation.

Summary

Memoization caches results of expensive function calls to avoid redundant computation.

Key Takeaways:

• Store computed results, lookup before recomputing
• Turns exponential → polynomial for overlapping subproblems
• Top-down approach to dynamic programming
• Needs pure functions with immutable inputs
• Common: Fibonacci, path counting, string matching
• Same power as tabulation, different style

Add memoization when you see repeated recursive calls with same arguments!