DPAlgorithmaka top-down DP, recursion with cache, memoized recursion

Memoization (Top-Down DP)

Write the natural recursion, then cache every result by its arguments so each distinct subproblem is computed once.

▶ Visualize Pattern: Dynamic Programming Practice (6)

Progress

Overview

Memoization turns a recursive function into a DP by adding a lookup table keyed on the arguments. Before computing, check the table; after computing, store. The recursion itself is unchanged, which is why memoization is the fastest route from "I see the recurrence" to a working, polynomial-time solution.

It is lazy: only the states actually reachable from the top query are evaluated. In problems where the reachable region is a small fraction of the full table (sparse knapsack capacities, digit DP with tight prefixes), memoization can be asymptotically cheaper than filling the whole table. The dependency order is discovered implicitly by the call stack — you never have to think about it.

Costs: recursion depth is bounded by the language stack (Python defaults to ~1000 frames; n = 10^5 states in a chain will overflow), function-call overhead is 2–5× a tight loop, and a hash-map memo is slower than an array. See Tabulation (Bottom-Up DP) for the bottom-up alternative and Dynamic Programming for the full framework.

top-downcacherecursionlazy evaluationhash map

Intuition

A mental model before the formal terms.

A student solving homework keeps a notebook. Each time a sub-question comes up they first flip to the notebook; if the answer is there they copy it, otherwise they work it out and write it down. The notebook is the memo; the flipping is the O(1) lookup that replaces an exponential recomputation.

For fib(6) the plain recursion tree has 25 calls. With a memo, the tree is pruned to one full path down the left spine plus one cheap lookup per node: 11 calls, and in general 2n - 1 calls instead of ≈ 1.6^n.

How it works

Write the brute-force recursive function solve(args) that returns the answer for a subproblem. Make sure it is a pure function of its arguments — no reliance on outside mutable state.
Choose the memo container: an array (or 2D array) indexed by the arguments when they are small dense integers; a hash map keyed on a tuple when they are sparse or non-integer.
At the top of solve: if memo[args] is set, return it. At the bottom: store the result in memo[args] before returning.
Use a sentinel that cannot be a legitimate answer (-1 for counts, None/undefined, a separate seen boolean array) so a stored 0 is not mistaken for "not computed".
If the recursion could be deep (> ~10^4 frames), either raise the recursion limit and use an explicit stack, or switch to Tabulation (Bottom-Up DP).

Why it works

Each distinct argument tuple triggers at most one real computation; every later call is an O(1) lookup. Total work is therefore (number of distinct states reached) × (cost of one transition), exactly the DP bound.

Correctness is identical to the plain recursion because the memo only substitutes an already-computed value for a value that would have been recomputed identically — the function is pure.

Recognition

How to tell a problem wants this.

You have a recurrence with a clear "smaller argument" structure and want the fastest correct implementation.
The state space is large but the reachable part is small (queries hit few states, or many (i, j) pairs are unreachable).
The natural dependency order is awkward to express as loops (intervals with irregular splits, tree children, digit DP with tight flags).

“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Fibonacci Numbers visualization.

n — Integer between 1 and 10

Call stack (top first)

fib(6)

n=6

Recursion tree

memo

n	fib(n)

1/23Call fib(6). Push a frame; the recursion tree grows one node.

Call in progressAnswered from memoReturned

PseudocodeLearn Fibonacci Numbers →

1fib(n):
2  if n <= 1: return n
3  if n in memo: return memo[n]
4  memo[n] = fib(n-1) + fib(n-2)
5  return memo[n]

Variables

depth1

Complexity

best O(n)

avg O(n)

worst O(n)

space O(1)

Speed

Pseudocode

1memo = empty map
2solve(state):
3  if state is a base case: return base value
4  if state in memo: return memo[state]
5  best = combine over choices of solve(smaller state)
6  memo[state] = best
7  return best

Implementations

1# Representative problem: n-th Fibonacci number with memoized recursion
2from functools import lru_cache
3import sys
4 
5sys.setrecursionlimit(10_000)           # default ~1000 frames is too small for fib(2000)
6 
7 
8def fib(n: int) -> int:
91 · Memo storage
10    memo: dict[int, int] = {}           # key: k, value: fib(k)
11 
12    def solve(k: int) -> int:
132 · Base cases
14        if k <= 1:
15            return k                    # fib(0) = 0, fib(1) = 1
163 · Cache lookup
17        if k in memo:
18            return memo[k]              # O(1) hit
194 · Compute and store
20        memo[k] = solve(k - 1) + solve(k - 2)
21        return memo[k]
22 
235 · Reset the memo and run
24    return solve(n)                     # memo is fresh per top-level call
25 
26 
27# Idiomatic Python: the decorator does the same thing automatically.
28@lru_cache(maxsize=None)
29def fib_cached(n: int) -> int:
30    return n if n <= 1 else fib_cached(n - 1) + fib_cached(n - 2)
31 
32 
33if __name__ == "__main__":
34    print(fib(50))         # 12586269025
35    print(fib_cached(50))  # 12586269025

Walkthrough

sys.setrecursionlimit(10_000) raises the default ~1000-frame cap; without it fib(1500) raises RecursionError.
The hand-written version uses a dict[int, int] closed over by the nested solve — k in memo is the presence test, so a cached 0 is safe.
memo[k] = solve(k - 1) + solve(k - 2) stores before returning; Python ints never overflow, so fib(500) is exact.
@lru_cache(maxsize=None) on fib_cached does exactly the same bookkeeping automatically, keyed on the argument tuple.
Both functions share the same recurrence and base cases; only the caching mechanism differs.

Complexity (this implementation)

time O(n) · space O(n) memo + O(n) recursion stack

Python frames are heavy (~500 bytes+) and slow; ~10^4–10^5 frames is the practical ceiling even after raising the limit.

Language notes

functools.lru_cache(maxsize=None) (or functools.cache in 3.9+) memoizes any function whose arguments are hashable — ints, strings, tuples; lists and dicts are not hashable.
For multi-dimensional states pass several ints or a tuple; the cache key is the argument tuple, so f(i, j) and f(j, i) are distinct entries.
Call f.cache_clear() between independent inputs when the cached function reads outer state, otherwise it returns stale answers.
Raising the recursion limit does not raise the C stack; extremely deep recursion can still segfault. Use threading.stack_size or tabulation for chains of 10^5+.

Common mistakes in this language

Forgetting sys.setrecursionlimit and getting RecursionError on moderately sized inputs.
Using if memo.get(k): — a cached 0 is falsy and gets recomputed.
Decorating a method that depends on mutable self state with lru_cache — the cache key does not include that state.
Passing a list as an argument to an lru_cached function (TypeError: unhashable type).

Language differences that matter here

Built-in memoization: Python has functools.lru_cache / functools.cache; C++, JS and TS have nothing built in — you write the lookup by hand.
Memo key for multi-dimensional states: Python hashes tuples natively; JS/TS Map compares arrays by reference, so build a string key (i + "," + j) or pack integers; C++ uses a nested vector, a packed 64-bit key, or std::map<std::pair<...>>.
Recursion depth: Python defaults to ~1000 frames (raise with sys.setrecursionlimit); JS/TS engines allow roughly 10^4; C++ depends on the OS stack (often ~10^5 small frames).
Value range: fib(93) overflows C++ long long; JS/TS numbers lose exactness past 2^53 (fib(79)); Python ints are unbounded.

Complexity

Best

—

Average

—

Worst

O(states × transition cost)

Space

O(states) memo + O(recursion depth) stack

Same asymptotic time as tabulation; constant factor higher (calls, hashing). Only reachable states are computed.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

You want a correct polynomial solution quickly from a known recurrence.
Only a fraction of the state space is reachable, so lazy evaluation saves real work.
The dependency order is irregular (interval splits, tree structure, digit-DP flags) and loops would be error-prone.

Avoid it when

Recursion depth would exceed the stack (chains of 10^5+ states) — use Tabulation (Bottom-Up DP).
Tight time limits where the 2–5× overhead of calls and hashing matters; a loop over an array is faster.
You need the space optimization (rolling rows) — that requires the explicit iteration order of bottom-up DP.

Alternatives

Tabulation (Bottom-Up DP)Recursion & Backtracking Dynamic Programming

Compare: Memoization vs Tabulation

Common mistakes

Using 0 as the "not computed" sentinel when 0 is a real answer — the cache never hits.
Keying the memo on fewer arguments than the function actually depends on (e.g. ignoring a mutable global), returning stale values.
Memoizing a function with side effects or that mutates its arguments (lists as keys, arrays modified during recursion).
Forgetting to raise Python's recursion limit, or ignoring stack limits entirely in deep chains.
Creating a fresh memo per top-level call in a loop of queries — reuse it across queries when the subproblems are shared.

Interview patterns

"Write brute force, then memoize" is the standard progression interviewers expect — narrate the recurrence, then the cache.
Use @lru_cache in Python for speed of writing; be ready to explain what it stores and why the key must be hashable.
Memoized DFS on a grid/graph with a "remaining budget" argument (word break with start index, longest increasing path in a matrix).

Interview questions on this

Deciding whether O(n²) can be improvedIntermediate
Choosing between BFS, DFS, Dijkstra and DPAdvanced
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Coin ChangeIntermediate

Example problems

Climbing Stairseasy House Robbermedium Coin Changemedium Word Breakmedium Edit Distancemedium Unique Pathsmedium

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related