Space Optimization Techniques
What you'll learn: How to dramatically reduce memory usage in dynamic programming solutions by keeping only the data you actually need.
The Core Idea
When building DP tables, you often don't need to store every previous result—just the ones that affect your current calculation. By analyzing which states depend on which others, you can throw away data that will never be used again, sometimes reducing space complexity from O(n²) or O(n·m) down to O(n) or even O(1).
Understanding Dependencies
Imagine calculating Fibonacci numbers with tabulation. To compute dp[i], you only need dp[i-1] and dp[i-2]. You never look back at dp[i-3] or earlier. So instead of keeping an entire array, you can maintain just two variables that "roll forward" as you compute.
Analogy: Think of a conveyor belt in a factory. If each station only needs parts from the previous two stations, you don't need to store materials from 100 stations back—just keep the last two within reach.
Common Patterns
1D array to variables: When dp[i] depends only on dp[i-1] and dp[i-2], replace the array with prev and curr variables.
2D array to 1D: If dp[i][j] only depends on row i-1 and the current row i, keep just two rows instead of the full matrix.
In-place updates: Sometimes you can reuse the same array by carefully ordering your computations.
When to Apply This
After you've solved a DP problem with tabulation, examine your state transitions. Ask: "How far back do I actually look?" If it's a fixed, small number of previous states, you can optimize.
Key Takeaway: Space optimization in DP means identifying and keeping only the previous states your transitions actually reference, often reducing memory from O(n²) to O(n) or O(n) to O(1).