Memoization

Tactic

Memoization is top-down dynamic programming. You write the natural recursive solution first, then cache the answer for each state so later calls return immediately.

The invariant is that a state is pure: the same state inputs always produce the same answer. If hidden mutable state changes the answer, the cache key is incomplete.

Memoization is often the fastest path from brute force to accepted DP. Keep the recursive meaning clear, choose a cache key, add base cases, and let the call graph visit only states that are actually reachable.

Value

The value is preserving the shape of the search while eliminating repeated work. It is easier to derive than tabulation for many tree, graph, string, and interval DP problems.

Direct complexity example

Brute force: Recursive backtracking recomputes the same state through many paths: often $O(2^n)$ time.
With this tactic: Cache each state after the first computation: $O(\text{states} \times \text{transition cost})$ time.
Space: Space includes the cache plus recursion stack. The stack is usually $O(\text{depth})$ and the cache is $O(\text{states})$ .

Challenges this solves

word break
decode ways
grid path counting
interval DP
recursive tree DP
DFS with repeated states

When to use it

Use this tactic when these conditions are true:

the recursive solution is obvious but too slow
subproblems repeat with the same parameters
not every table state is reachable
the dependency order is awkward to write bottom up

When not to use it

Reach for a different tactic when these warning signs appear:

the function depends on mutable global state not included in the key
recursion depth exceeds language limits
every state is required and tabulation would be simpler
memory for the cache is larger than the input constraints allow

Terminology clues

These prompt words often point toward this concept:

cache
top-down
same state
repeated calls
DFS plus memo
lru_cache
overlapping
state tuple