Space optimization
Overview
If `dp[i]`'s transition only reads a FIXED small window of previous states, you don't need to keep the whole table. A few rolling variables or rows will suffice.
It reduces the space complexity of bottom-up DP significantly. A 1D array collapses from O(n) space to O(1) space, and a 2D matrix collapses from O(m*n) to O(n) space.
Why learn this
- In an interview, coming up with the O(n) space DP is the pass. Reducing it to O(1) space is the strong hire.
- Space-optimized DP is often used in real memory-constrained environments where allocating a huge matrix is impossible.
Common mistakes
- Applying it blindly to unbounded lookbacks: If `dp[i]` depends on a value arbitrarily far back in the table (like in Longest Increasing Subsequence, where `dp[i]` checks every `j < i`), you cannot collapse it to a fixed window. It only works if the lookback distance is a constant.
- Losing the ability to reconstruct the path: When you space-optimize, you throw away older states. You only retain the numeric answer. If the problem asks you to return the actual path (e.g. which items were selected), you cannot space-optimize without extra bookkeeping.
Recall questions
- What is the generalizable rule for when you can space-optimize a DP table?
- What is the primary trade-off of space optimization?
- How does a 2D grid DP table (like unique paths) space-optimize?
Understanding checks
A DP algorithm uses a 1D array where `dp[i]` is computed using only `dp[i-1]`, `dp[i-2]`, and `dp[i-3]`. What is the minimum space complexity we can achieve?
O(1)
The transition only looks back 3 steps. We can maintain 3 rolling variables instead of an array of size `n`. 3 variables is a constant, hence O(1) space.
A developer space-optimizes a knapsack DP to one row, but iterates left-to-right. Why does this give the wrong answer for 0/1 knapsack?
Iterating left-to-right overwrites the row with current-item data, so cells later in the row read values that ALREADY include the current item.
0/1 knapsack requires the item to be used at most once. By scanning right-to-left, we ensure we only read the PREVIOUS item's state before we overwrite it.
Practice tasks
Analyze space optimization applicability
Look at this recurrence: `dp[i] = dp[i-1] + max(dp[0...i-2])`. Can you space-optimize this to O(1) variables?
Continue learning
Previous: Tabulation (bottom-up)
Next: Climbing stairs / Fibonacci
Next: House robber