Dynamic Programming • Bitmask

State Compression (Profile DP)

Use an integer bitmask to represent a complex boundary state (like a jagged edge in a grid tiling problem) allowing O(1) state transitions.

Try Interactive Simulator

Overview

Also known as "Broken Profile DP". If you are filling a grid column by column, the boundary between the filled and unfilled sections can be jagged.

The Mask

Since the grid height `M` is usually very small (e.g., M ≤ 15), we can represent the jagged boundary as an `M`-bit integer. `1` means filled, `0` means empty.

Transitions

From `dp[col][mask]`, we try placing blocks that fill the `0`s in the current `mask`. Any blocks that spill over into the NEXT column will create the `next_mask`.

The Goal

We usually want to tile the entire grid perfectly. This means we want the answer at `dp[N][0]` (after processing all N columns, 0 bits spill over into the void).

Col 1

000

Col 2

000

Col 3

000

Code Tracker

:::

1// Tiling example: dp[col][mask]

2dp[0][0] = 1;

3for (let i = 0; i < N; i++) {

4 for (let mask = 0; mask < (1 << M); mask++) {

5 if (dp[i][mask] > 0) {

6 // Try all valid ways to tile this column

7 // resulting in next_mask for column i+1

8 dp[i + 1][next_mask] += dp[i][mask];

9 }

10 }

11}

12return dp[N][0];

State Compression Dp

State Compression Dp

State Compression (Profile DP)

Overview

The Mask

Transitions

The Goal

State Compression (Profile DP)

Overview

The Mask

Transitions

The Goal