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;
}
}