Space Optimization
Space optimization keeps only the DP states that future transitions can still read, replacing full tables with rolling arrays or variables when dependencies are local.
Optimize After Correctness
Space optimization should come after the state and transition are correct. The full table is easier to reason about, easier to debug, and easier to explain. Once the dependency pattern is clear, ask which old states are still needed by future computations.
If no future transition will read a state again, it can be discarded. This is the entire principle behind rolling arrays and rolling variables.
From 2D to 1D
A two-dimensional DP can collapse to one dimension when each row depends only on the previous row and maybe the current row. Unique Paths can keep one row because each cell uses the value above and the value to the left. 0-1 Knapsack can keep one capacity array when capacities are iterated backward so each item is used at most once.
Loop direction is critical. Backward capacity iteration preserves the previous row for 0-1 choices. Forward capacity iteration is appropriate for unbounded choices where reusing the same item is allowed.
From 1D to O(1)
A one-dimensional DP can collapse to variables when each state depends on a fixed number of previous states. Climbing Stairs needs only the previous two values. House Robber needs the best value excluding and including the current position through a rolling pair.
Do not compress if the transition reads an unbounded set of earlier states unless you have another data structure to summarize them. Optimization should preserve the same dependency information, not hope the missing values are unnecessary.
How to Explain It
Interviewers want to hear the dependency argument. Say which previous cells the transition reads, how long those cells remain needed, and why overwriting is safe. If using a one-dimensional array for a two-dimensional DP, explicitly justify loop direction.
A good explanation for Climbing Stairs is: dp[i] reads only dp[i - 1] and dp[i - 2], so after computing the next value, all older states can be discarded.
Before and after rolling variables
Both versions compute the same recurrence. The optimized version keeps only the two states that the next transition can read.
Key Takeaways
- Optimize space only after the full DP dependency pattern is correct.
- A 2D table can become 1D when transitions need only the previous row or controlled current-row values.
- A 1D table can become O(1) when each state depends on a fixed-size window.
- Loop direction is part of correctness whenever overwriting a rolling array.