Tabulation

Bottom-up DP: fill a table in an order that guarantees every dependency is ready. No recursion, no call overhead, and space optimisation becomes easy.

Converting from memoization

Mechanical, in three steps:

1. Identify the dependency direction. If solve(i) calls solve(i-1), then $i$ must increase. If it calls solve(i+1), $i$ must decrease.
2. Reverse it into a loop. Iterate so dependencies are computed first.
3. Move the base cases out of the recursion and into the array’s initial values.

// memoized
long long solve(int i) {
    if (i == 0) return 0;
    return max(solve(i-1), solve(i-2) + a[i]);
}
 
// tabulated
dp[0] = 0; dp[1] = a[1];
for (int i = 2; i <= n; i++) dp[i] = max(dp[i-1], dp[i-2] + a[i]);

Getting the order right

This is the only genuinely hard part. The rule: the loop order must be a topological order of the state dependency graph.

Recurrence shape	Loop order
dp[i] from dp[i-1]	$i$ increasing
dp[i] from dp[i+1]	$i$ decreasing
dp[i][j] from dp[i-1][*]	outer $i$ increasing, inner $j$ anything
dp[i][j] from dp[i][j-1] and dp[i-1][j]	both increasing
Interval DP: dp[l][r] from shorter intervals	by increasing length, then by $l$
Tree DP: dp[v] from children	post-order, or reverse BFS order
Bitmask DP: dp[mask] from submasks	mask increasing (submasks are numerically smaller)
Knapsack 0/1 with 1D array	weight decreasing
Unbounded knapsack with 1D array	weight increasing

The last two are the classic trap. In 0/1 knapsack, iterating weights upward would let the same item be used twice, because dp[w - wt] would already reflect this item. Iterating downward reads the previous row’s values. In unbounded knapsack you want that reuse, so you iterate upward. Same code, opposite loop direction, completely different problem.

// 0/1: each item once
for (int i = 0; i < n; i++)
    for (int w = W; w >= wt[i]; w--)            // DOWN
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
 
// unbounded: unlimited copies
for (int i = 0; i < n; i++)
    for (int w = wt[i]; w <= W; w++)            // UP
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

Push vs pull

Two ways to write the same DP:

// PULL: compute dp[i] from its predecessors
for (int i = 1; i <= n; i++)
    for (auto p : predecessors(i)) dp[i] = min(dp[i], dp[p] + cost(p, i));
 
// PUSH: propagate dp[i] to its successors
for (int i = 0; i <= n; i++)
    for (auto s : successors(i)) dp[s] = min(dp[s], dp[i] + cost(i, s));

Pull matches the recursive definition and is easier to reason about. Push is often easier to write when the successors are simple and the predecessors are awkward to enumerate — grid moves, coin choices, graph edges. Use whichever makes the inner loop natural.

Why tabulation is worth the trouble

	Benefit
Speed	2-5× faster; no call overhead, better cache locality
Space	rolling arrays reduce $O(nW)$ to $O(W)$
Vectorisation	tight loops get auto-vectorised; recursion does not
No stack limits	works at any depth
Bitset tricks	bitset DP requires a flat array layout

The costs are that you must derive the order yourself, and you compute every state — even unreachable ones. When the reachable fraction of the state space is tiny, memoization wins.

Iteration order and cache

For large 2D tables, iterate the last index in the inner loop so memory access is sequential. Swapping the loops on a $5000\times 5000$ table can cost a 5-10× slowdown from cache misses alone — enough to turn an accepted solution into a TLE.

See also: Memoization · Space Optimization · Introduction to DP