Space Optimization Patterns

1. Rolling Arrays

for i in rows:
  cur = [...]
  for j in cols:
    cur[j] = f(prev[j], prev[j-1], cur[j-1])
  prev = cur

2. Bitmask Compression

Represent subset / boolean states in integer bits. Iterate masks and submasks efficiently.

mask = (1<<n)-1
sub = mask
while sub:
  process(sub)
  sub = (sub-1) & mask

3. Prefix / Difference Arrays

Use prefix sums to collapse an extra dimension of range-dependent transitions.

4. Windowed States

Maintain only k previous rows/columns with deque or circular buffer if transition depends on bounded window.

5. Closed Forms

Some recurrences reduce to math formula (e.g., Fibonacci, sums of arithmetic/geometric progressions) removing DP entirely.