Refactoring: Space Optimized DP

The bottom-up Fibonacci uses an array of size N+1. But we only ever need the last two values. By keeping only what's necessary, we go from O(N) memory to O(1). This pattern — "keep the sliding window" — applies to almost every linear DP.

Before: Full Array Tabulation

C++ — O(N) memory

int fib(int n) {
    if (n <= 1) return n;
    vector dp(n + 1);  // ← stores EVERYTHING
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// n = 10⁷:  dp array = 40 MB  (just for fibonacci!)

🚨 Memory waste

At any point, we only need dp[i-1] and dp[i-2] to compute dp[i]. The entire history is irrelevant. Storing all N values is wasteful and limits input size.

After: O(1) Space with Rolling Variables

C++ — O(1) memory

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;  // dp[i-2], dp[i-1]
    for (int i = 2; i <= n; i++) {
        int c = a + b;  // dp[i]
        a = b;
        b = c;
    }
    return b;
}

// n = 10⁷:  3 int variables = 12 bytes

Rust — O(1) memory

fn fib(n: u64) -> u64 {
    if n <= 1 { return n; }
    let (mut a, mut b) = (0, 1);
    for _ in 2..=n {
        let c = a + b;
        a = b;
        b = c;
    }
    b
}

💡 The rolling variable pattern

dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k]) — if the recurrence only looks back K steps, you only need K variables. This is called "rolling DP" or "space-optimised DP." Always ask: "do I really need the whole table?"

Key Takeaways