# State Compression DP

## Summary

State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning.

## OJ

TrickDifficulty
LC 1349. Maximum Students Taking Exam DP State Compression + Bit Manipulation6 points
LC 691. Stickers to Spell WordDP State Compression 6-7 points
LC 1411. Number of Ways to Paint N × 3 GridDP State Compression or Direct DP 6 points
LC 943. Find the Shortest SuperstringDP State Compression + TSP7 points
LC 1434. Number of Ways to Wear Different Hats to Each OtherDP Knapsack + State Compression6-7 points

## Details

#### LC 1349. Maximum Students Taking Exam

Difficulty: 6 points.

We could use bit manipulation and state compression DP. For each row, when a slot has a student we consider the corresponding bit to be 1, so there are at most `2^n` states for each row. Some bit manipulation tricks are as following.

``````// row curr does not contain adjacent students
// row curr does not occupy '#'
// forbidden[i] = 101101 for 'x.xx.x'
inline bool ok(bitset<8> const &curr, int i) {
return (curr & (curr >> 1)) == 0 && (i >= 0 ? (forbidden[i] & curr) == 0 : true);
}

// row curr and row prev does not contain diagonal students
inline bool ok(bitset<8> const &curr, bitset<8> const &prev) {
return ((curr >> 1) & prev) == 0 && ((curr << 1) & prev) == 0;
}``````

Then the DP state transformation is not difficult.

``````alg[i][prev] =
max {curr.count() + alg[i + 1][curr] if ok(curr, prev) && ok(curr, i) && ok(prev, i - 1) for curr in [0, (1 << n) - 1]}``````

Note that for the DP table related to previous state, we need to find answer by adding at least one state. However, here we know `alg` will work since the first row won’t have conflicts with previous state `0`.

#### LC 1411. Number of Ways to Paint N × 3 Grid

Difficulty: 6 points.

This problem can be solved efficiently in `log(n)` time, which is introduced in this post. It is nice to mention as a follow up solution.

The common answer will be State Compression for this kind of problem. The grid is of length 3, which means a grid has 27 states. We use a base 3 number integer to represent states, though we need to explicitly parse the physical meaning out of the integer (no base 2 tricks here).

``alg[i][prev] = sum { alg[i + 1][curr] if ok(curr, prev) && ok(prev) && ok(curr) for curr in [0, 27]``

Note that for the DP table related to previous state, we need to find answer by adding at least one state.

``````ll result = 0;
for (int prev = 0; prev < 27; ++prev) {
result += alg[prev];
result %= MOD;
}
return result;``````

#### LC 943. Find the Shortest Superstring

Difficulty: 7 points.

The problem is hard, since it is hard to detect it is actually a TSP problem.

Think in this way. Given a permutation of strings, if between two adjacent strings there are overlaps, we could leverage them and shorten the total length. For example, `"catg" + "atgcatc"` can be `"c" + "atg" + "catc"`. We want to maximize the overlaps. In the other way, if we think the non-overlapping chars as the cost to stick the current word to the previous one. The problem becomes find out a permutation with lowest cost, which is a TSP problem.

Regarding the TSP problem, for any permutation, the cost starting from index j is determined by the visited indexes and the previous index i. Visited indexes could use the State Compression technique.

The problem also needs to output a path. So we uses another table to store our best choices at each state.

``````alg[visited][prev] =
min {alg[visited | 1 << j][j] + dist[prev][j] if ((1 << j) & visited == 0 && (1 << prev) & visited > 0) for j in [0, n - 1]}

choices[visited][prev] =
argmin {alg[visited | 1 << j][j] + dist[prev][j] if ((1 << j) & visited == 0 && (1 << prev) & visited > 0) for j in [0, n - 1]}``````

Note that for the DP table related to previous state, we need to find answer by adding at least one state.

``````int min_ = INT_MAX;
int curr = -1;
for (int i = 0; i < n; ++i) {
if (alg[1 << i][i] + A[i].size() < min_) {
min_ = alg[1 << i][i] + A[i].size();
curr = i;
}
}``````