13.3 Memoization

Once a state and recurrence have been defined, the most direct way to implement a dynamic programming solution is memoization. Memoization starts from the original recursive formulation of a problem and adds a cache that remembers previously computed results. Whenever the same subproblem appears again, the stored answer is returned immediately instead of recomputing it.

Memoization is often the easiest way to convert an exponential recursive algorithm into a polynomial-time dynamic programming solution. It preserves the natural structure of the recurrence while eliminating redundant work.

Problem

Given a recursive recurrence relation with overlapping subproblems, how can we avoid recomputing identical states?

Understanding Overlapping Subproblems

Consider the Fibonacci recurrence:

$$ F(n)=F(n-1)+F(n-2) $$

A naive recursive implementation repeatedly solves the same subproblems.

For example:

F(6)
├── F(5)
│   ├── F(4)
│   │   ├── F(3)
│   │   └── F(2)
│   └── F(3)
└── F(4)
    ├── F(3)
    └── F(2)

Notice that:

F(4)
F(3)
F(2)

appear multiple times.

The recursive algorithm performs the same computations repeatedly.

The number of calls grows exponentially.

The Core Idea

Store the result of each state after computing it.

When the state is requested again:

return cached value

instead of:

recompute recursively

This simple modification transforms many exponential algorithms into polynomial-time solutions.

Recipe 1: Cache Every State

Start with the recursive recurrence.

For Fibonacci:

$$ F(n)=F(n-1)+F(n-2) $$

Add a cache:

var memo map[int]int

func fib(n int) int {
    if n <= 1 {
        return n
    }

    if v, ok := memo[n]; ok {
        return v
    }

    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
}

Each state is computed once.

All future requests become constant-time lookups.

Complexity Transformation

Without memoization:

$$ T(n)=T(n-1)+T(n-2) $$

Complexity:

$$ O(2^n) $$

With memoization:

States:

$$ n+1 $$

Each state computed once:

$$ O(n) $$

The improvement is dramatic.

Example: Staircase Problem

Problem:

You may climb 1 or 2 steps.
Count ways to reach step n.

State:

$$ dp[i] $$

Meaning:

number of ways to reach step i

Recurrence:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Memoized implementation:

func ways(i int, memo map[int]int) int {
    if i <= 1 {
        return 1
    }

    if v, ok := memo[i]; ok {
        return v
    }

    memo[i] = ways(i-1, memo) + ways(i-2, memo)

    return memo[i]
}

Every staircase size is evaluated exactly once.

Example: Coin Change

Problem:

Minimum coins needed
to form amount x

State:

$$ dp[x] $$

Recurrence:

$$ dp[x] = 1+ \min(dp[x-c]) $$

for every valid coin value (c).

Memoized implementation:

func solve(amount int) int {
    if amount == 0 {
        return 0
    }

    if amount < 0 {
        return inf
    }

    if v, ok := memo[amount]; ok {
        return v
    }

    best := inf

    for _, coin := range coins {
        best = min(
            best,
            solve(amount-coin)+1,
        )
    }

    memo[amount] = best
    return best
}

Large recursion trees collapse into a small collection of cached states.

Example: Longest Common Subsequence

State:

$$ dp[i][j] $$

Meaning:

LCS length
between prefixes
A[0...i]
B[0...j]

Recurrence:

If characters match:

$$ dp[i][j] = 1+dp[i-1][j-1] $$

Otherwise:

$$ dp[i][j] = \max ( dp[i-1][j], dp[i][j-1] ) $$

Memoization stores each pair:

(i,j)

after its first computation.

Instead of exploring exponentially many recursive paths, the algorithm evaluates at most:

$$ O(nm) $$

states.

Memoization and State Graphs

Every dynamic programming problem can be viewed as a graph.

Vertices:

states

Edges:

transitions

Without memoization:

same vertex visited repeatedly

With memoization:

each vertex processed once

Memoization performs a depth-first traversal of the state graph while caching results.

Memoization Template

Most memoized solutions follow the same structure.

func solve(state State) Result {

    if isBaseCase(state) {
        return baseAnswer
    }

    if value, found := memo[state]; found {
        return value
    }

    answer := combine(
        solve(smallerState1),
        solve(smallerState2),
        ...
    )

    memo[state] = answer

    return answer
}

This pattern appears throughout dynamic programming.

Choosing a Cache Structure

Arrays

When state indices are contiguous.

Example:

memo := make([]int, n+1)

Advantages:

Fastest access
Excellent cache locality
Minimal overhead

Hash Maps

When states are sparse.

Example:

memo := make(map[State]int)

Advantages:

Flexible
Handles arbitrary states
Memory efficient for sparse state spaces

Multidimensional Arrays

Example:

memo := make([][]int, n)

Useful for:

grids
sequences
interval DP

Detecting Memoization Opportunities

Memoization works best when both conditions hold.

Optimal Substructure

Solutions depend on smaller solutions.

Example:

shortest path
knapsack
LCS

Overlapping Subproblems

Same states appear repeatedly.

Example:

F(5)

may appear dozens of times during recursion.

Without overlap, memoization provides little benefit.

Memoization vs Ordinary Caching

Memoization is a specialized form of caching.

Ordinary caching:

store arbitrary results

Memoization:

store results of pure subproblems

A memoized state should always produce the same answer.

This deterministic property guarantees correctness.

Common Mistakes

Forgetting to Store Results

solve(...)

is computed repeatedly.

Performance remains exponential.

Incorrect State Keys

Example:

store only position

when answer also depends on:

remaining capacity

Different subproblems overwrite each other.

Mutable State

If a state contains mutable data:

lists
maps
objects

hashing and equality become error-prone.

Prefer immutable state representations.

Missing Base Cases

Memoization does not eliminate the need for valid stopping conditions.

Infinite recursion still occurs.

Memory Considerations

Memoization stores every reachable state.

Memory complexity:

$$ O(S) $$

where:

$$ S $$

is the number of distinct states.

Sometimes:

time decreases dramatically
memory increases significantly

This tradeoff is fundamental to dynamic programming.

Memoization Advantages

Natural Implementation

The code mirrors the mathematical recurrence.

Easy to Write

No dependency ordering is required.

Computes Only Needed States

Unreachable states are never evaluated.

Excellent for Complex State Spaces

Tree DP, graph DP, digit DP, and game search often begin with memoization.

Memoization Disadvantages

Recursion Overhead

Function calls introduce extra cost.

Stack Depth Limits

Deep recursion may overflow the call stack.

Less Predictable Memory Access

Cached states may be visited in irregular order.

Harder to Optimize

Advanced space optimizations are usually easier with tabulation.

Complexity Analysis

Let:

$$ S $$

be the number of distinct states.

Let:

$$ K $$

be the transition cost.

Each state is computed once.

Total running time:

$$ O(S \times K) $$

Memory usage:

$$ O(S) $$

These formulas characterize most memoized dynamic programming algorithms.

Takeaway

Memoization transforms recursive recurrences into efficient dynamic programming solutions by caching previously computed states. Each state is evaluated at most once, eliminating redundant computation caused by overlapping subproblems. The resulting implementation closely follows the mathematical recurrence, making memoization one of the most effective and intuitive ways to develop dynamic programming solutions before moving to iterative tabulation techniques.