Overlapping Subproblems and Memoization

The fastest way to feel why dynamic programming exists is to write a function that is correct but painfully slow, watch exactly where it wastes its time, then fix it with a few lines. Fibonacci is the classic case: short enough to hold in your head, slow enough to make the point.

The naive version, and why it crawls

Each Fibonacci number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. That definition is also a working program.

calls = 0

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

print(fib(30), "computed in", calls, "calls")

832040 computed in 2692537 calls

What just happened: computing fib(30) took over 2.6 million function calls to produce one number. The reason is that fib(30) calls fib(29) and fib(28), but fib(29) also calls fib(28), and both of those call fib(27), and so on. The same subproblems get solved again and again down separate branches of the call tree. That repeated work is called overlapping subproblems, and it makes the running time grow like O(2^n) - roughly double for every step up.

📝 Terminology. Overlapping subproblems means the recursive calls keep asking the same questions. If each subproblem were unique (like the two halves in merge sort), there would be nothing to cache and DP would not help. Overlap is the thing dynamic programming exploits.

The fix: remember what you already computed

The wasted work is entirely re-computation. fib(28) has one answer; there is no reason to derive it more than once. So keep a dictionary - a memo - mapping each n to its answer. Before computing fib(n), check the memo. Compute it only on a miss, and store the result on the way out.

calls = 0

def fib(n, memo=None):
    global calls
    calls += 1
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(30), "computed in", calls, "calls")

832040 computed in 59 calls

What just happened: same answer, but 59 calls instead of 2.6 million. Each distinct subproblem fib(2) through fib(30) is computed exactly once and cached; every other request is an instant memo hit. This top-down style - ordinary recursion plus a cache - is called memoization. The running time drops from O(2^n) to O(n), because there are only n distinct subproblems and each costs constant work once its inputs are known.

💡 Key point. Memoization does not change what the function computes - only how many times it computes each piece. You keep the readable recursive definition and bolt a cache onto it.

⚠️ Gotcha: the mutable default argument. Do not write def fib(n, memo={}). In Python a default argument is created once and shared across every call, so the memo would persist between unrelated top-level calls and quietly leak state. The memo=None then if memo is None: memo = {} pattern gives each fresh call its own memo. (Python's own functools.lru_cache decorator sidesteps this entirely and is what you would use in real code.)

The same memoized Fibonacci, in other languages

The shape is identical everywhere: a base case, a cache lookup, compute-and-store on a miss. Only the cache type and the syntax change. Flip through the tabs.

[[codegroup Memoized Fibonacci]]

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

function fib(n, memo = {}) {
  if (n < 2) return n;
  if (n in memo) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

function fib(n: number, memo: Record<number, number> = {}): number {
  if (n < 2) return n;
  if (n in memo) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

static long fib(int n, Map<Integer, Long> memo) {
    if (n < 2) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.put(n, result);
    return result;
}

long long fib(int n, std::unordered_map<int, long long>& memo) {
    if (n < 2) return n;
    if (memo.count(n)) return memo[n];
    long long result = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = result;
    return result;
}

func fib(n int, memo map[int]int) int {
    if n < 2 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

use std::collections::HashMap;

fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n < 2 {
        return n;
    }
    if let Some(&v) = memo.get(&n) {
        return v;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

[[/codegroup]]

The typed languages pass the memo in by reference (&, &mut, or a shared object) so that every branch of the recursion writes into the same cache - exactly what makes the caching work. Pass a copy per call and you are back to the slow version.

Check yourself

[
  {
    "q": "What makes naive recursive Fibonacci exponentially slow?",
    "choices": ["It uses too much memory per call", "The same subproblems like fib(28) get recomputed on many separate branches", "Recursion is always slower than a loop", "Python function calls are unusually slow"],
    "answer": 1,
    "explain": "fib(30) and fib(29) both need fib(28), and so on down the tree - the same subproblems are solved again and again, doubling the work at each level."
  },
  {
    "q": "What does memoization store, and keyed by what?",
    "choices": ["The entire call stack", "The final answer only", "The answer to each subproblem the first time it is computed, keyed by that subproblem's inputs", "A log of every function ever called"],
    "answer": 2,
    "explain": "A memo maps a subproblem's inputs to its answer, so the second request for the same inputs is an instant lookup instead of a recomputation."
  },
  {
    "q": "Memoized Fibonacci turns the running time from O(2^n) into roughly what?",
    "choices": ["O(1)", "O(log n)", "O(n)", "O(n^2)"],
    "answer": 2,
    "explain": "There are only n distinct subproblems; each is computed once and every other request is a cache hit, so total work is proportional to n."
  }
]