Memoization

Top-down DP: write the recursion naturally, then cache. The order of evaluation takes care of itself.

The template

vector<vector<long long>> memo;
vector<vector<bool>> done;
 
long long solve(int i, int j) {
    if (/* base case */) return /* base value */;
    if (done[i][j]) return memo[i][j];
    done[i][j] = true;
    long long res = NEG_INF;
    for (/* each choice */) res = max(res, solve(/* smaller state */) + gain);
    return memo[i][j] = res;
}

Using a separate done array rather than a sentinel value avoids the classic bug where a legitimate answer happens to equal your “not computed” marker.

For sparse or irregular state spaces, use a hash map instead of an array:

unordered_map<long long, long long> memo;
long long key = (long long)i * M + j;          // pack the state
if (memo.count(key)) return memo[key];

Why memoization first

When you are unsure of a recurrence, memoization lets you write the definition of the problem and get a working solution. Only after it is correct do you worry about converting to tabulation for speed or space.

The conversion is mechanical: read off the dependency direction from the recursive calls and loop in the opposite order.

The three costs of memoization

1. Function call overhead. Typically 2-5× slower than the equivalent loop. Often irrelevant, occasionally fatal.
2. Stack depth. Deep recursion overflows. If the state chain can be $10^6$ long, either convert to tabulation or explicitly raise the stack.
3. Clearing between test cases. With multiple test cases, clearing a large memo array every time can dominate the runtime.

The version-stamp trick

Instead of clearing, stamp each entry with the test-case number:

int stamp[N][M], curTest = 0;
long long memo[N][M];
// per test case: curTest++;
if (stamp[i][j] == curTest) return memo[i][j];
stamp[i][j] = curTest;

$O(1)$ per test case instead of $O(NM)$. This is worth knowing whenever a problem has many small test cases.

Memoization on non-numeric states

Anything hashable works as a key — strings, tuples, canonical board positions, tree hashes. This is where top-down genuinely beats bottom-up: there is often no sensible way to enumerate such states in order, but there is always a way to recurse into them.

map<string, int> memo;
int solve(const string& state) {
    if (memo.count(state)) return memo[state];
    ...
}

Game solving, puzzle search, and “count distinct configurations” problems all live here.

Common bugs

Bug	Symptom
Caching before the base-case check	wrong answers on trivial inputs
A parameter that affects the answer but is not in the key	wrong answers, non-reproducible
A parameter in the key that does not affect the answer	correct but far too slow
Forgetting to reset between test cases	first test right, rest wrong
Sentinel value collides with a real answer	recomputation or wrong answer
Recursion on a cyclic state graph	infinite loop — you need Dijkstra or Bellman-Ford, not DP

That last row is worth internalising: memoization silently assumes the state graph is acyclic. If a state can depend on itself (directly or through a chain), memoization loops forever or returns garbage.

Reconstructing the solution

Either store a choice[i][j] array during the computation, or re-derive it afterwards by replaying the recurrence and checking which branch achieves the memoised value. The second uses no extra memory and is usually simpler to write correctly.

See also: Tabulation · Introduction to DP · Space Optimization