State Compression

State compression reduces a large or awkward state description into a smaller representation.

It is often used in dynamic programming when the straightforward state would be too expensive.

Core Idea

The algorithm keeps only the information needed for future decisions. Extra history is removed or encoded compactly.

Bitmasks are a common form of state compression, but compression can also mean reducing a DP table from two rows to one row when only the previous row is needed.

Python Example

def climb_stairs_compressed(n):
    previous = 1
    current = 1
 
    for _ in range(2, n + 1):
        previous, current = current, previous + current
 
    return current

The full DP table is compressed to two variables because only the previous two states are needed.

Common Confusions

State compression should not remove information that future transitions need. If two different situations have different futures, they cannot be safely merged.

Compression can make code harder to read. It is often better to write the clear full-state version first.

When To Use It

Use state compression when the uncompressed DP is correct but too large, and when the recurrence proves that only a smaller part of the state is needed.