Space Optimization

DP tables often exceed the memory limit long before the time limit becomes a problem. Most of the table is usually unnecessary.

Rolling arrays

If dp[i][*] depends only on dp[i-1][*], keep two rows:

vector<long long> prev(m + 1), cur(m + 1);
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) cur[j] = f(prev[j], prev[j-1], cur[j-1]);
    swap(prev, cur);
}

$O(nm)\to O(m)$. If the dependency spans $k$ rows, keep $k+1$ and index with i % (k+1).

Single array, careful direction

When the recurrence reads only smaller indices in the same row, one array suffices — but the loop direction decides which row you are reading:

// 0/1 knapsack: read the PREVIOUS row -> iterate down
for (int i = 0; i < n; i++)
    for (int w = W; w >= wt[i]; w--)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
 
// unbounded knapsack: read the CURRENT row -> iterate up
for (int i = 0; i < n; i++)
    for (int w = wt[i]; w <= W; w++)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

This is the most important space optimisation in competitive programming, and also the most common source of subtle wrong answers.

Bitsets for boolean DP

When dp[j] is a boolean “is sum $j$ achievable”, a bitset gives a 64× speedup and 64× memory reduction:

bitset<MAXSUM + 1> dp;
dp[0] = 1;
for (int x : items) dp |= dp << x;             // subset sum, O(n * SUM / 64)
bool canMake = dp[target];

$O(n\cdot \text{SUM})$ becomes $O(n\cdot \text{SUM}/64)$, which turns $10^{10}$ into $1.5\cdot 10^8$. See Bitset Optimization.

Smaller types

int instead of long long halves the table. short, char, or even packed nibbles work when the value range is small. Check for overflow before doing this — the saving is not worth a wrong answer.

Divide and conquer for the traceback

The hardest case: you need the actual solution, not just its value, and the table does not fit. Hirschberg’s algorithm solves this for alignment problems in $O(nm)$ time and $O(\min (n,m))$ space by recursively finding where the optimal path crosses the middle row.

The same idea — recompute rather than store — applies whenever the traceback is the only reason you were keeping the table.

Recomputation instead of storage

If reconstructing a decision is cheap, do not store it:

// instead of choice[i][j], re-derive it:
for (auto opt : choices(i, j))
    if (dp[i][j] == value(opt) + dp[next(i, j, opt)]) { take(opt); break; }

Costs one extra evaluation per step of the traceback, saves an entire table.

Memory budget table

Type	Elements in 256 MB
bool / char	$2.6\cdot 10^8$
short	$1.3\cdot 10^8$
int / float	$6.7\cdot 10^7$
long long / double	$3.3\cdot 10^7$
bitset bits	$2.1\cdot 10^9$

Rules of thumb: a long long table of $5000\times 5000$ is 200 MB — too big. The same table as int is 100 MB — borderline. Rolled to two rows, it is 40 KB.

vector<bool> is not an array of bool

It is a bit-packed specialisation, so it is 8× smaller but slower per access and cannot give you a pointer to an element. For a DP table it is usually the right choice for memory; for hot inner loops prefer bitset (faster, fixed size) or vector<char>.

Choosing

1. Does the recurrence look back only one row? → rolling array.
2. Is the value boolean? → bitset.
3. Do you need the path? → traceback by recomputation, or Hirschberg.
4. Still too big? → the state itself is wrong; revisit state design.

See also: Tabulation · Bitset Optimization · Hirschberg