Memoization

Memoization stores the result of a function call so the same call does not need to be recomputed.

It is the top-down style of dynamic programming.

Core Idea

The recursive function keeps its natural shape. Before solving a state, it checks whether the answer is already stored. If it is, the function returns the stored value.

Memoization is often the easiest way to turn a slow recursive solution into a dynamic programming solution.

Memoization is useful when recursion expresses the problem clearly but repeats states. The cache changes the cost by making each distinct state compute only once.

Function Contracts

fib(n) expects a non-negative integer and returns the nth Fibonacci number while caching repeated calls.

can_make_sum(values, target) expects positive numbers and a non-negative target. It returns whether some subset of the values can add exactly to target.

Python Example

from functools import lru_cache
 
@lru_cache(None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

lru_cache stores results by function argument.

Manual Cache Version

The same idea can be written with a dictionary:

def fib(n):
    memo = {}
 
    def solve(k):
        if k <= 1:
            return k
        if k in memo:
            return memo[k]
 
        memo[k] = solve(k - 1) + solve(k - 2)
        return memo[k]
 
    return solve(n)

The cache key is k because k fully determines the answer for this subproblem.

State as Function Arguments

For more complex problems, the recursive function may take several arguments:

from functools import lru_cache
 
def can_make_sum(values, target):
    @lru_cache(None)
    def solve(index, remaining):
        if remaining == 0:
            return True
        if index == len(values) or remaining < 0:
            return False
 
        skip = solve(index + 1, remaining)
        take = solve(index + 1, remaining - values[index])
        return skip or take
 
    return solve(0, target)

The pair (index, remaining) is the state. It fully describes which part of the list is still available and how much sum is still needed.

Complexity

Memoization makes each distinct state compute at most once. For fib(n), the distinct states are 0 through n, so the time and cache space are O(n).

For can_make_sum, there can be up to len(values) * (target + 1) distinct (index, remaining) states when values are positive and remaining stays between 0 and target.

Common Confusions

Memoization does not remove recursion depth. A deeply recursive memoized function can still hit Python’s recursion limit.

The arguments must fully describe the state. If important information is hidden in mutable global data, the cache may return the wrong answer.

Arguments used with lru_cache must be hashable. Lists and dictionaries cannot be cache keys directly. Convert them to tuples or encode the needed information another way.

When To Use It

Use memoization when the recursive structure is clear and the same states are reached repeatedly.

It is often the best first DP implementation because it lets the recurrence stay close to the problem’s natural recursive explanation.

The Main Point

Memoization keeps the recursive explanation but stores each distinct state once. The cache key must fully describe the state.