## 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

Trick | Difficulty | |
---|---|---|

LC 1349. Maximum Students Taking Exam | DP State Compression + Bit Manipulation | 6 points |

LC 691. Stickers to Spell Word | DP State Compression | 6-7 points |

LC 1411. Number of Ways to Paint N × 3 Grid | DP State Compression or Direct DP | 6 points |

LC 943. Find the Shortest Superstring | DP State Compression + TSP | 7 points |

LC 1434. Number of Ways to Wear Different Hats to Each Other | DP Knapsack + State Compression | 6-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[0][0]`

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[1][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;
}
}
```