Pattern Guide
DP Space Optimization
"Rolling array: reduce O(n²) DP space to O(n) or O(1). Fill order matters."
Many 2D DP tables can be compressed to 1D by observing that each row only depends on the previous row. The key: when dp[i][j] depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], we can use a 1D array if we process in the right order. Traversal direction (left-to-right vs right-to-left) determines whether we use the new or old row's values.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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];
}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 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];
}- 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.