Pattern Reference
DP Space Optimization
"Rolling array, 1D to O(1) space, Knuth optimization, monotone queue optimization, divide & conquer optimization."
Loading...
Deep Dive Tutorial
Space compression rule: if dp[i][j] depends only on row i-1, use one row. Overwrite from left-to-right when you need dp[i-1][j-1] (old diagonal) — BUT it gets overwritten, so save prev diagonally or use two arrays. Classic trick: LCS can use 1 row with careful ordering. 0/1 Knapsack: traverse weight right-to-left so items aren't counted twice.
LCS and 0/1 knapsack with O(n) space
// LCS with O(min(m,n)) space — 1D rolling array
function lcs(s, t) {
const m = s.length, n = t.length;
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prev = 0; // dp[i-1][j-1]
for (let j = 1; j <= n; j++) {
const temp = dp[j]; // save dp[i-1][j] before overwrite
if (s[i-1] === t[j-1]) dp[j] = prev + 1;
else dp[j] = Math.max(dp[j], dp[j-1]);
prev = temp; // prev becomes dp[i-1][j] for next iteration
}
}
return dp[n];
}
// 0/1 Knapsack with O(W) space — process weights right-to-left
function knapsack(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// Right-to-left: ensures each item used at most once
for (let w = W; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
return dp[W];
}Worked Problems
save
Space compression rules:
- Row depends on previous row only → 1D rolling array
- Cell uses diagonal (i-1,j-1): save in
- 0/1 knapsack (each item once): iterate weights right-to-left
- Unbounded knapsack (infinite items): iterate weights left-to-right
When NOT to compress: When you need to reconstruct the solution (backtrack through DP table) — keep 2D array or store choices separately.
Maximal Square trick: dp[j] = min(left, above, diagonal) + 1. The three neighbors in 2D compress elegantly to three accessible values in 1D + prev variable.
- Row depends on previous row only → 1D rolling array
- Cell uses diagonal (i-1,j-1): save in
prev variable before overwriting- 0/1 knapsack (each item once): iterate weights right-to-left
- Unbounded knapsack (infinite items): iterate weights left-to-right
When NOT to compress: When you need to reconstruct the solution (backtrack through DP table) — keep 2D array or store choices separately.
Maximal Square trick: dp[j] = min(left, above, diagonal) + 1. The three neighbors in 2D compress elegantly to three accessible values in 1D + prev variable.