Memoization
Dynamic Programming solves complex problems by breaking them down into overlapping subproblems. Memoization does this top-down with recursion; Tabulation does it bottom-up with loops.
Paying Once for Each Subproblem
Memoization caches the result of a function call so that repeating the same call returns the stored value instead of recomputing it. Applied to a recursion whose subproblems repeat, it converts exponential work into polynomial.
The canonical demonstration is Fibonacci. fib(n) = fib(n-1) + fib(n-2) written directly makes about 1.6 million calls for n = 30 and roughly 2.7 billion for n = 45 — yet there are only n distinct values to compute. Everything beyond those n calls is recomputation of results already derived elsewhere in the tree.
Adding a cache collapses this. Each distinct value of n is computed once and read thereafter, so the call count drops from O(2ⁿ) to O(n). The recursive structure is untouched; three lines are added.
The precondition is overlapping subproblems — the same subproblem must be reached along different branches. Without overlap there is nothing to reuse and the cache is pure overhead. Merge sort recurses too, but its halves are disjoint and never recur, which is why it is divide and conquer rather than dynamic programming.
So memoization is not a general speedup. It is the answer to one specific waste: a recursion tree that revisits the same states. Recognising that shape — an exponential brute force whose branches converge — is what tells you the technique applies.
The general cost formula follows directly: number of distinct states × work per state. Fibonacci has n states and O(1) work each, giving O(n). A two-parameter recursion over an n × m grid has n·m states, giving O(n·m).
- Cache results so each distinct subproblem is computed once
- Fibonacci drops from O(2ⁿ) calls to O(n)
- Requires overlapping subproblems — otherwise it is pure overhead
- Cost is the number of distinct states times the work per state
Choosing the Key
The cache key is the design decision, and getting it wrong produces bugs that are hard to trace because the code still returns plausible answers.
The key must capture every parameter the result depends on — and nothing more.
Too little, and different situations collide on one entry. A function taking (index, remainingCapacity) but keyed only on index returns whatever answer was stored for a different capacity. The result is wrong, not slow, and it is wrong only on inputs where both parameters vary.
Too much, and the state space explodes. Including a parameter that does not affect the result — the accumulated path so far, when only its length matters — means no two calls ever share a key, so the cache never hits and the recursion stays exponential while also consuming memory.
The test that resolves it: if you paused the function here, what would you need to know to finish correctly? Exactly that set is the key. In the knapsack problem it is the current item index and the remaining capacity — which items were already taken does not matter, only the capacity they consumed.
Practical forms of the key vary by language. A tuple of the parameters is idiomatic in Python and hashes naturally. A multidimensional array indexed by the parameters is faster when the parameters are small non-negative integers, avoiding hashing entirely. A string built from the parameters works but is slow and worth avoiding.
One trap deserves naming: mutable parameters cannot be keys. A list passed into a memoized function cannot be hashed in Python, and even where it can be, mutating it afterwards leaves a stale entry keyed on a value that no longer exists. Convert to a tuple, or key on an index into the unchanging structure instead.
- Key on exactly what the result depends on — no more, no less
- Too few parameters conflate states; too many prevent any cache hit
- Ask what you would need to know to finish from here
- Mutable values cannot be keys — use tuples or indices
Against Tabulation
Memoization is top-down: write the natural recursion, add a cache. Tabulation is bottom-up: allocate a table, fill the base cases, and loop over the states in an order guaranteeing every dependency is ready before it is needed. Both compute the same values; they differ in direction and in what that costs.
Memoization's advantages are real. It is easier to derive — get a correct recursion first, then add three lines, with no reordering. And it computes only the states actually reachable from the input, which on a sparse problem can be a small fraction of the table. A recursion over a grid that can only move right and down never visits most of the table's cells, and tabulation would fill them anyway.
Its costs are the recursion. Stack depth can reach the state-space depth, and languages with modest limits overflow — Python's default is 1000 frames, raising RecursionError. Raising the limit with sys.setrecursionlimit works up to a point but risks a genuine segfault, so an iterative rewrite is the safer answer for deep states. There is also call overhead, making memoization a constant factor slower than the equivalent loop.
Tabulation's advantages mirror these: no stack risk, tighter loops, and — the significant one — the possibility of rolling arrays. When each row of the table depends only on the previous row, the full table is unnecessary: keep two rows, or iterate one row in the right direction and keep one. This takes knapsack from O(n·W) space to O(W), an optimisation memoization cannot easily match because the recursion may request any state at any time.
Its cost is that you must derive the fill order yourself, and getting it wrong reads a cell before it is written — silently, producing an answer built on zeros.
The practical route through an unfamiliar problem: write the brute-force recursion, add memoization, confirm correctness, and convert to tabulation only if the depth or the constant factor demands it.
| Memoization | Tabulation | |
|---|---|---|
| Written as | Recursion plus a cache | Loops filling a table |
| States computed | Only reachable ones | All of them |
| Ordering | Handled by the recursion | You must derive it |
| Stack risk | Overflow on deep states | None |
| Speed | Call overhead | Usually faster |
| Space tricks | Hard | Rolling arrays |
- Memoization derives easily and skips unreachable states
- Tabulation avoids the stack and enables rolling arrays
- Deriving the fill order is tabulation's cost
- Recursion first, memoize, then tabulate only if needed
Memoized Fibonacci cache hits and misses
cache = {0: 0, 1: 1}
def fib(n):
if n in cache:
return cache[n]
cache[n] = fib(n - 1) + fib(n - 2)
return cache[n]
print("fib(6) =", fib(6))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
map<int,int>c=
{
{
0,0
}
,
{
1,1
}
};
int fib(int n)
{
if(c.count(n))return c[n];
return c[n]=fib(n-1)+fib(n-2);
}
int main()
{
cout<<"fib(6) = "<<fib(6);
}import java.util.*;
class Main
{
static Map<Integer,Integer>c=new HashMap<>();
static int fib(int n)
{
if(c.containsKey(n))return c.get(n);
int v=fib(n-1)+fib(n-2);
c.put(n,v);
return v;
}
public static void main(String[]z)
{
c.put(0,0);
c.put(1,1);
System.out.print("fib(6) = "+fib(6));
}
}Step through it
Running on fib(6)
Read all 14 Steps
- Call fib(6) The cache starts empty.
- Cache miss 6 Compute dependencies 5 and 4.
- Miss 5 fib(5) is not cached.
- Miss 4 fib(4) is not cached.
- Miss 3 fib(3) is not cached.
- Reach base cases fib(1)=1 and fib(0)=0 need no recursion.
- Store fib(2) Store 1 for state 2.
- Store fib(3) Store 2 for state 3.
- Cache hit fib(2) A repeated request returns 1 immediately.
- Store fib(4) Store 3 for state 4.
- Cache hit fib(3) A repeated request returns 2 immediately.
- Store fib(5) Store 5 for state 5.
- Cache hit fib(4) The second fib(4) request is another hit.
- Store fib(6) 5+3=8; cache state 6 and return.
Practical Cache Management
Most languages provide memoization as a decorator or wrapper, and using it is usually better than hand-rolling. Python has functools.cache for an unbounded cache and functools.lru_cache(maxsize=N) for a bounded one. Java typically uses a HashMap explicitly or Guava's caches. C++ uses an unordered_map or a plain array when the states are small integers.
An array beats a hash map whenever the parameters are small non-negative integers: no hashing, contiguous memory, and O(1) indexing. Reach for a map only when the state space is sparse or the keys are not integers.
When using an array, the sentinel for 'not yet computed' must be a value the function can never legitimately return. Using 0 is the standard mistake in problems where 0 is a valid answer, causing correct results to be recomputed indefinitely — or, worse, a genuine 0 to be treated as absent. Use −1 for non-negative results, or a separate boolean array when no safe sentinel exists.
Cache lifetime is the issue that shows up outside interviews. A cache attached to a function persists across calls, so memoizing a function whose result depends on anything other than its arguments — a global, a file, the current time — returns stale answers indefinitely. Memoization is only correct for pure functions.
The related failure is unbounded growth. A cache keyed on user input in a long-running service grows without limit and is a memory leak with extra steps. Bound it with an LRU policy, or scope the cache to a single top-level call and discard it afterwards. In competitive programming with multiple test cases, clearing the cache between cases is essential — a cache carrying values from the previous input produces answers that look random.
A final note on what memoization does not fix: it removes repeated work, not excessive work. If a recursion has exponentially many distinct states, caching them all is exponential in memory and does not help. That situation calls for a better formulation — a smaller state, or a different algorithm entirely.
- Use an array over a hash map when the parameters are small integers
- Pick a sentinel the function can never legitimately return — not 0
- Memoize only pure functions, or the cache serves stale results
- Clear or bound the cache; an unbounded one is a memory leak