Space Optimization (rolling, bit tricks)

Space optimization reduces memory—rolling DP arrays, bitsets instead of bool lists, in-place reversal tricks. Often trades time for space or vice versa.

Why this shows up in the real world

Embedded devices squeeze KB-level RAM. GPU kernels reuse registers aggressively.

Core idea (explained for students)

If dp[i] depends only on dp[i-1], keep two rows. Store indices instead of full objects when only order matters.

Try this in Python

def fib_two_vars(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_two_vars(10))

Common mistakes

• Overwriting DP rows still needed for reconstruction—keep parent pointers separately if paths matter.
• Python int bitsets still use memory—know object overhead.

Key takeaways

• Profile RSS vs algorithmic clarity; sometimes two rows is enough win.
• Use generators to pipeline without huge lists when consumers are incremental.