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.

Function Contract

climb_stairs_compressed(n) expects a non-negative integer n.

It returns the number of ways to reach step n while keeping only the two most recent DP states instead of the full table.

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.

Row Compression

For a grid or string DP, sometimes the current row depends only on the previous row. Then a full n * m table can be compressed to two rows:

previous = [0] * cols
current = [0] * cols

After finishing a row, current becomes previous for the next row.

Why Compression Is Safe

Compression is safe only when discarded information will never be needed again. The recurrence must prove that future states depend only on the retained part.

If a later step needs an older value, compressing it away makes the algorithm wrong.

Complexity Effect

State compression often keeps time the same while reducing memory. For example, O(n) memory can become O(1), or O(nm) memory can become O(m).

Verification Step

Before compressing, write down which previous states the recurrence reads. If it reads only the previous row, keep one or two rows. If it reads arbitrary older states, compression may not be safe.

The compressed version should be treated as an optimization of a known-correct full-state version.

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.

Another common mistake is updating a compressed array in the wrong direction. In knapsack, loop direction determines whether an item can be reused.

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.

Do not start with compression when learning a new DP. First make the state and recurrence correct.

The Main Point

State compression is safe only when the discarded information will never be needed by future transitions.