🎓 A1Learner
🔍
0 of 47 lessons completed

Memoization: Remembering Subproblems

Memoization is the technique of storing answers to subproblems so each one is solved only once. A stored answer is returned at once when the same subproblem appears again.

The recognition signal

A problem needs a memo when the same subproblem is solved many times. The plain recursive climb below counts how often that happens.

calls = 0


def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


print("Ways:", ways(10))
print("Calls without a memo:", calls)

The memoization template

The lru_cache helper stores each answer after its first computation. Later calls with the same input return the stored answer at once.

from functools import lru_cache

calls = 0


@lru_cache(maxsize=None)
def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


print("Ways:", ways(10))
print("Calls with a memo:", calls)

Worked problem: steps of 1, 2, or 3

With steps of 1, 2, or 3, the plain recursion repeats heavily. The memo keeps one answer per step, so the count for 10 steps is found fast.

from functools import lru_cache


@lru_cache(maxsize=None)
def ways(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    return ways(n - 1) + ways(n - 2) + ways(n - 3)


print("Ways to climb 10 steps:", ways(10))

Example

from functools import lru_cache

nums = [2, 7, 9, 3, 1]


@lru_cache(maxsize=None)
def best(i):
    if i < 0:
        return 0
    if i == 0:
        return nums[0]
    return max(best(i - 1), best(i - 2) + nums[i])


print("Best total:", best(4))

Key points

  • A memo is a record that maps each input to its solved answer.
  • Use the memo to check before computing and to store after computing.
  • The helper functools.lru_cache can supply the memo automatically.
  • Memoization turns repeated work into a quick lookup of answers already found.

Each index is solved once and its answer is stored. Skipping a house keeps the best total up to the previous house. Taking a house adds its value to the best total up to two houses back. The stored answers give 12.

Note

memoization keeps the recursive shape of the recurrence and adds memory.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What does a memo store?