Space Optimization in Dynamic Programming

The Core Idea: Analyzing State Dependencies

The opportunity for space optimization arises from a simple observation about the transition function in many DP problems. To figure out if you can optimize, you should always ask yourself:

"To compute the value for the current state, which of the previously computed states do I actually need?"

Often, the answer is "not all of them."

As the video highlights, if the calculation for dp[i] only depends on dp[i-1] and dp[i-2], there's no need to keep dp[0] through dp[i-3] in memory. This dependency analysis is the key that unlocks space optimization.

Technique 1: Variable Reduction in 1D DP

Let's start with the familiar Fibonacci sequence, which we used as a running example. In the previous lesson, we ended with a sneak peek of this very optimization. Now, let's formalize it.

The recurrence relation is:

Our standard bottom-up (tabulation) approach uses an array of size $O(n)$ to store all values from dp[0] to dp[n]. However, the recurrence clearly shows that to compute dp[i], we only need the two immediately preceding values.

This means we can discard the $O(n)$ array and use just a few variables to keep track of the necessary states as we iterate.

To summarize the logic shown in the video, we can implement the Fibonacci function iteratively like this (using Python for illustration):

def fib_optimized(n):
    if n <= 1:
        return n




    # We only need the previous two values, not a full array
    prev2 = 0  # Represents dp[i-2]
    prev1 = 1  # Represents dp[i-1]

    for i in range(2, n + 1):
        current = prev1 + prev2  # Calculate dp[i]
        



        # 'Roll' the variables forward for the next iteration
        prev2 = prev1
        prev1 = current
        
    return prev1 # prev1 holds the final result, fib(n)

By doing this, we have reduced the auxiliary space complexity from $O(n)$ to $O(1)$, as we are only using a fixed number of variables regardless of the input n. This is a massive improvement.

Technique 2: The Rolling Array in 2D DP

The same principle applies to multi-dimensional DP, but the implementation is slightly different. The most common pattern is the rolling array, used to optimize problems that would typically require a 2D DP table.

Consider a classic problem: counting the number of unique paths on an N x M grid from (0, 0) to (N-1, M-1), where you can only move right or down.

The recurrence relation for the number of paths to cell (i, j) is:

A naive tabulation approach would use an N x M table, for a space complexity of $O(N\cdot M)$.

However, notice the dependency: to compute any cell in the current row i, we only need values from the previous row i-1 and the current row i itself (specifically, the cell to the left). We never need to look at rows i-2, i-3, etc.

This allows us to optimize. Instead of storing the full N x M grid, we only need to store two rows: the one we just finished calculating (previous_row) and the one we are currently calculating (current_row).

The logic described in the document can be implemented as follows:

1. Create a previous_row array of size M, representing the results for row i-1. Initialize it based on the problem's base cases.
2. Start a loop for i from 1 to N-1.
3. Inside the loop, create a current_row array of size M.
4. Loop j from 0 to M-1 to fill current_row:
   • current_row[j] is calculated using previous_row[j] (the cell above) and current_row[j-1] (the cell to the left).
5. After the inner loop finishes, the current_row is complete. Now, for the next iteration (for row i+1), this current_row becomes the previous_row. So, set previous_row = current_row.
6. After the outer loop finishes, the answer is in the last element of the final previous_row.

This rolling array technique reduces the space complexity from $O(N\cdot M)$ to $O(M)$, since we only ever store one or two rows at a time. If M is much smaller than N, we can iterate over columns instead of rows to achieve $O(\min (N,M))$ space.

To see this pattern in code, here is an example of optimizing the Edit Distance problem, another classic 2D DP problem.

Conclusion

You have now completed the foundational toolkit for dynamic programming. You can identify problems suitable for DP, formulate recursive solutions, convert them to top-down memoization or bottom-up tabulation, analyze their complexity, and, finally, optimize their space usage.

Key Takeaways:

• Space optimization in DP is possible when the transition to a new state depends on a limited number of previous states.
• The first step is always to analyze the dependencies in the recurrence relation.
• For 1D DP problems like Fibonacci, where dp[i] depends on dp[i-1] and dp[i-2], we can often use simple variables to reduce space from $O(n)$ to $O(1)$.
• For 2D DP problems where dp[i][j] depends on the previous row (i-1), we can use a rolling array to reduce space from $O(N\cdot M)$ to $O(M)$ or $O(\min (N,M))$.

Preview of the Next Module:
With these fundamental techniques under your belt, you are now ready to tackle a range of classic algorithmic challenges. The next module, Classic Dynamic Programming Applications, will be dedicated to applying everything we've learned. We will start by solving the famous 0/1 Knapsack problem, a quintessential DP problem that showcases these concepts in action.