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

Leave a Reply

Your email address will not be published. Required fields are marked *