Course contentsShow
← Computer Science
Lesson 922 of 2,87222. Dynamic ProgrammingFree lesson

Space Optimization Techniques

Reduce memory usage by observing dependencies and keeping only necessary previous states in the table.

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).