memoization
Memoization is the trick of letting a function remember the results it has already computed, so that a repeated call returns the saved answer instantly instead of doing all the work again. The name comes from memo — a note to self. It is dynamic programming worn top-down: you keep your natural recursive solution, but the first time you compute the answer for a given input you tuck it into a cache (a hash table or an array), and every later call for that same input is a quick lookup.
The textbook illustration is Fibonacci. The plain recursion fib(n) = fib(n-1) + fib(n-2) is correct but disastrous: it recomputes the same values an exponential number of times, costing about O(2^n). Add a cache — check it before recursing, store the result before returning — and every fib(k) is computed exactly once. The running time collapses to O(n), because there are only n distinct subproblems and each is solved a single time; you spend O(n) extra memory to hold the answers.
Memoization shines when a recursion has overlapping subproblems but you would rather not rewrite it as a bottom-up loop. It computes only the subproblems you actually reach (unlike tabulation, which fills the whole table), which can be a real win when the reachable states are sparse. The price is the memory of the cache plus a little lookup overhead, and you must be careful to key the cache on everything that affects the answer — get the key wrong and you will happily return a stale, incorrect result.
vector<long long> memo; // memo[i] = -1 means "not computed yet"
long long fib(int n) {
if (n < 2) return n;
if (memo[n] != -1) return memo[n]; // cache hit
return memo[n] = fib(n - 1) + fib(n - 2); // compute once, store
}
// init: memo.assign(n + 1, -1);Turns the O(2^n) naive recursion into O(n) — each subproblem is solved exactly once.
Memoization (top-down) and tabulation (bottom-up) are the two standard implementations of dynamic programming. Memoization is just adding a cache to a recursion; tabulation rebuilds the same answers iteratively. Reach for memoization when the recursion is already clear and only some states are actually needed.