Skip to content

State Compression DP

Introduction

State Compression DP is a type of dynamic programming that achieves state transitions by converting a set of states into integers recorded in the DP state.

To achieve lower time complexity, it is usually necessary to find states with a lower number of states. In most problems, binary states are utilized, using an \(n\)-bit binary number to represent \(n\) independent binary states.

Using state compression typically involves bitwise operations. For basic bitwise operations, refer to the Bit Operations page.

Example 1

「SCOI2005」Mutual Non-aggression

Place \(K\) kings on an \(N\times N\) chessboard (\(1 \leq N \leq 9, 1 \leq K \leq N \times N\)) such that they do not attack each other. How many placement schemes are there?

A king can attack the eight squares adjacent to it: up, down, left, right, and the four diagonal directions.

Explanation

Let \(f(i,j,l)\) represent the number of valid placement schemes for the first \(i\) rows, with the state of the \(i\)-th row being \(j\), and \(l\) kings already placed on the board.

For a state numbered \(j\), we use the binary integer \(sit(j)\) to represent the placement of kings. A binary digit of \(0\) in \(sit(j)\) indicates no king in the corresponding position, while \(1\) indicates a king placed. Let \(sta(j)\) denote the number of kings in this state, i.e., the count of \(1\)s in the binary number \(sit(j)\). For example, as shown in the figure below, the state can be represented by the binary number \(100101\) (the left side of the board corresponds to the lower bits of the binary number). Thus, \(sit(j)=100101_{(2)}=37\) and \(sta(j)=3\).

Let the current row's state be \(j\) and the previous row's state be \(x\). The state transition equation is: \(f(i,j,l) = \sum f(i-1,x,l-sta(j))\).

Let the previous row's state number be \(x\). Under the condition that the current row and the previous row do not conflict, enumerate all possible \(x\) for transition. The transition equation is:

\[ f(i,j,l) = \sum f(i-1,x,l-sta(j)) \]

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;

void dfs(int x, int num, int cur) {
  if (cur >= n) {  // New valid state found
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // Do not place king at position cur
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // Place king at position cur, adjacent positions cannot have kings
}

bool compatible(int j, int x) {
  if (sit[j] & sit[x]) return false;
  if ((sit[j] << 1) & sit[x]) return false;
  if (sit[j] & (sit[x] << 1)) return false;
  return true;
}

int main() {
  cin >> n >> k;
  dfs(0, 0, 0);  // Preprocess all valid states for a single row
  for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
      for (int x = 1; x <= cnt; x++) {
        if (!compatible(j, x)) continue;  // Exclude invalid transitions
        for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
      }
  long long ans = 0;
  for (int i = 1; i <= cnt; i++) ans += f[n][i][k];  // Accumulate the answer
  cout << ans << endl;
  return 0;
}

Example 2

[POI2004] PRZ

There are \(n\) people who need to cross a bridge. The \(i\)-th person has weight \(w_i\) and crossing time \(t_i\). These people will be divided into several groups when crossing the bridge. Only after all members of a group have crossed can the remaining groups proceed. The bridge has a maximum load capacity \(W\). What is the minimum total time for all people to cross the bridge?

\(100\le W \le 400\), \(1\le n\le 16\), \(1\le t_i\le 50\), \(10\le w_i\le 100\).

Explanation

Let \(S\) represent a subset of all people. Define \(t(S)\) as the longest crossing time among people in \(S\), \(w(S)\) as the total weight of people in \(S\), and \(f(S)\) as the minimum total time for all people in \(S\) to cross the bridge. Then:

\[ \begin{cases} f(\varnothing)=0,\\ f(S)=\min\limits_{T\subseteq S;~w(T)\leq W}\left\{t(T)+f(S\setminus T)\right\}. \end{cases} \]

Note that we cannot directly enumerate a set and then check if it is a subset. Instead, we should use subset enumeration to achieve a time complexity of \(O(3^n)\).

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int W, n;
  cin >> W >> n;
  const int S = (1 << n) - 1;
  vector<int> ts(S + 1), ws(S + 1);
  for (int j = 0, t, w; j < n; ++j) {
    cin >> t >> w;
    for (int i = 0; i <= S; ++i)
      if (i & (1 << j)) {
        ts[i] = max(ts[i], t);
        ws[i] += w;
      }
  }
  vector<int> dp(S + 1, numeric_limits<int>::max() / 2);
  for (int i = 0; i <= S; ++i) {
    if (ws[i] <= W) dp[i] = ts[i];
    for (int j = i; j; j = i & (j - 1))
      if (ws[i ^ j] <= W) dp[i] = min(dp[i], dp[j] + ts[i ^ j]);
  }
  cout << dp[S] << '\n';
  return 0;
}

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用