Memoization and introductory dynamic programming

You have written recursive functions that break a big problem into smaller copies of itself. Some of those functions solve the same smaller problem many times over, without ever noticing, and the recursion tree grows out of control as a result.

MemoizationmemoizationStoring the result of each distinct call to a recursive function the first time it runs, so a later call with the same arguments is looked up instead of recomputed.In the glossary fixes this directly: remember the answer to each subproblem the first time you compute it, and look it up instead of recomputing it every other time it comes up. That one change can turn an exponential recursion into one that finishes almost instantly.

The problem with repeated work

You are on stair 0 of a staircase, and each step forward moves you up 1 or 2 stairs. How many different sequences of steps reach stair 5 or beyond?

1def count_ways(stair):2    if stair >= 5:3        return 14    return count_ways(stair + 1) + count_ways(stair + 2)

This is correct: the number of ways to finish from a stair is the ways from one step ahead plus the ways from two steps ahead, and once you have reached or passed the top there is exactly one way to be there. But trace the calls, and count_ways(2) gets computed once from count_ways(0)'s first branch, and again from count_ways(1)'s second branch. The same subproblem is solved from scratch every time it is needed, and the number of calls roughly doubles with every stair you add. On a staircase of 20 steps, this recursion makes over a million calls to answer a question with only 21 distinct subproblems.

Memoization: remembering subproblem answers

Keep a cache of results you have already computed. Before doing any work, check whether the cache already has the answer; only recurse if it does not, and store the result before returning it.

1memo = {}2
3def count_ways(stair):4    if stair >= 5:5        return 16    if stair in memo:7        return memo[stair]8    result = count_ways(stair + 1) + count_ways(stair + 2)9    memo[stair] = result10    return result

Now each stair is computed exactly once. The first call to count_ways(2) does the work and stores the answer; every later call, from wherever it comes, finds it already sitting in memo.

1memo = {}2
3
4def count_ways(stair):5    if stair >= 5:6        return 17    if stair in memo:8        return memo[stair]9    result = count_ways(stair + 1) + count_ways(stair + 2)10    memo[stair] = result11    return result12
13
14print(count_ways(0))

13

Follow one path through the cache to see why this is enough. count_ways(0) calls count_ways(1) and count_ways(2). count_ways(1) in turn calls count_ways(2) again, but this time it is already cached, so the second branch of count_ways(0) costs nothing. Every stair from 0 to 4 is solved once and reused everywhere it is needed afterward, and the recursion returns 13, the number of distinct step sequences from stair 0 to stair 5. The total work is proportional to the number of distinct stairs, not the size of the uncached recursion tree.

From memoized recursion to dynamic programming

Memoization solves the problem top-down: start at the original question and work outward to smaller pieces, caching as you go. You can flip that around and solve it bottom-up instead: start from the subproblems you already know the answer to, and build outward toward the one you want.

1dp = [0] * 72dp[6] = 13dp[5] = 14
5for stair in range(4, -1, -1):6    dp[stair] = dp[stair + 1] + dp[stair + 2]7
8print(dp[0])

dp[i] holds the number of ways to finish from stair i. Stairs 5 and 6 are the base cases: landing on either one is a completed climb, so both are filled in directly as 1. Every earlier stair adds the answers from the two stairs reachable in one step, computed in order from stair 4 down to stair 0, so both values it needs are always ready by the time they are used. This prints the same 13 as the memoized version above, built in a fixed order instead of on demand.

Both versions do the same amount of work, one subproblem at a time. Memoization figures out which subproblems it needs as it recurses; dynamic programming decides the order in advance and fills a table.

A second example: coin change

Suppose you have coins worth 1, 5 and 10, and you want the fewest coins that add up to 23. Always taking the biggest coin you can is not safe here: 10 + 10 + 1 + 1 + 1 uses five coins, but so does 10 + 5 + 5 + 1 + 1 + 1, so a greedy rule is not obviously correct and needs checking against alternatives, which means trying options rather than assuming one.

The minimum coins for amount A is 1 plus the minimum coins for whichever of A - 1, A - 5 or A - 10 needs the fewest, provided that amount is not negative. Amount 0 needs zero coins, and a negative amount is impossible, so it is excluded rather than counted. Without a cache, this recursion revisits the same amounts from many different paths, exactly like the staircase problem. With one, each amount gets solved a single time, no matter how many paths lead to it.

Getting these right

Check the cache before you do any recursive work, not after. Checking afterward means every call still pays the full cost the first time through, and you only save time on a second, separate call to the exact same subproblem.

Define the cache outside the function so it survives across calls. A dictionary created inside the function body gets rebuilt empty on every call, which throws away everything memoization is supposed to save.

And get the base case exactly right before you add caching on top of it. A base case that is off by one, such as stair >= 5 written as stair > 5, changes which stair is treated as "already at the top," and the wrong count will look plausible enough to miss on a quick read. Test the base case on a tiny version of the problem by hand first.

Why this matters

The cache costs space: one entry per distinct subproblem, so K subproblems need O(K) memory. In exchange, the time drops from however many times the naive recursion revisits the same work down to O(K) calls total, since each one now runs once. For the 20-step staircase, that is the difference between roughly a million calls and 21.

Whenever a recursive solution is correct but too slow, ask whether it is solving the same subproblem more than once. If it is, memoization or its bottom-up twin, dynamic programming, is usually the fix that gets it to run in time.