Dynamic Programming I: Memoization

The same work, done a million times

Recall the Fibonacci numbers: each is the sum of the previous two. The textbook recursion writes itself: `fib(n) = fib(n-1) + fib(n-2)`. Clean and correct — and catastrophically slow. The reason is that the same subproblems get recomputed again and again. Draw the call tree for `fib(5)` and you'll see `fib(2)` computed *three separate times*, from scratch, each time.

                       fib(5)
                      /       \
                 fib(4)        fib(3)
                /     \        /     \
           fib(3)   fib(2)  fib(2)  fib(1)
           /    \
       fib(2)  fib(1)        <- fib(2) appears 3 times total,
                                fib(3) appears twice ... and it
                                doubles with every step of n.

Two properties make this fixable, and together they are the signature of a [[dynamic-programming|dynamic programming]] problem. First, overlapping subproblems: the same smaller problems show up over and over (that repeated `fib(2)`). Second, optimal substructure: the answer to the big problem is built directly from the answers to smaller ones. When you spot both, you have a DP problem on your hands.

Memoization: write the answer down

[[memoization|Memoization]] is the simplest possible fix, and it keeps your nice recursive code almost intact. You add a cache — a place to store each answer the first time you compute it. Then every call does just two new things: *check the cache before working*, and *store the result before returning*. That's the entire trick.

#include <vector>

long long fib(int n, std::vector<long long>& memo) {
    if (n <= 1) return n;                 // base cases
    if (memo[n] != -1) return memo[n];    // 1) cache hit: reuse
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // 2) store
    return memo[n];
}

long long fib(int n) {
    std::vector<long long> memo(n + 1, -1);  // -1 = "not computed yet"
    return fib(n, memo);
}

Why O(n)? Because there are only `n+1` distinct subproblems (`fib(0)` through `fib(n)`), and the cache guarantees each is *actually computed* only once — every later request is an instant lookup. We traded a little memory (the array) for an astronomical amount of time. That trade — space for time — is the heart of every DP.

When the state isn't a plain integer

An array memo works when the subproblem is identified by a small integer. But often the state — the bundle of values that pins down one subproblem — is something else: a pair `(i, j)`, a string, a position-plus-a-budget. When a plain index won't do, reach for a hash map: `std::unordered_map`. The key is whatever uniquely names the subproblem.

#include <unordered_map>
#include <string>

std::unordered_map<std::string, long long> memo;

long long solve(int i, int j) {
    std::string key = std::to_string(i) + "," + std::to_string(j);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;   // cache hit

    long long result = /* ... combine subproblems of (i,j) ... */ 0;
    memo[key] = result;                         // store before returning
    return result;
}

Memoization, step by step

Here is the whole recipe you can apply to any DP problem from the top down. Notice it's nothing more than "write the honest recursion, then bolt a cache onto it." You don't have to be clever about the order things get computed — the recursion figures that out for you.

1. Write the plain recursion first: base cases, then "answer = combine(smaller answers)".
2. Identify the state — the minimal values that name one subproblem. That's your cache key.
3. Create a cache: an array if the state is a small int, an unordered_map otherwise.
4. At the top of the function, return the cached answer if it exists.
5. Before each return, store the computed answer in the cache. Done.