Bit DP Problems
Published:
Bit DP is use a binary number to represent a state which a state is consisted of several varying substate(likely two states on and off), we use bit 1, 0 to represent these varying substates.
Usually these states need to be validated thus we may need following tricks:
1) i_{th} bit of state is 1 or 0: (state » 1 & 1) == 1 or (state » 1 & 1) == 0 2) state has adjacent 1’s bits: (state & state » 1) == 1 3) state i is a subset of j: i & j == i (when some bit of i is 1, then j will at least be 1 at that bit)
Example:
- Maximum Students Taking Exam
since the result of how to take the seats of one row is only determined by previous row, we can use dp and use bit to represent how the seats are taken in one row.
valid states satify: 1) not in the adjacent columns of the prev row, if seats taken; 2) no seats taken in adjacent columns. we use bit mask trick mentioned to validate and do the dp from 1st to the last row.
DP transition: dp[i][j] = dp[i-1][k] + bits_count_of(j) if state j is valid and (i, j) are also valid
Java code:
class Solution {
public int maxStudents(char[][] seats) {
int m = seats.length, n = seats[0].length;
int[][] dp = new int[m+1][1<<n];
int[]st = new int[m+1];
st[0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = n-1; j >= 0; j--)
if (seats[i-1][j] == '.') {
st[i] |= (1 << (n-1-j));
}
System.out.println(Integer.toBinaryString(st[i]));
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= st[i]; j++) {
if ((j & st[i]) == j && (j & j >> 1) == 0) {
for (int k = 0; k <= st[i-1]; k++) {
if ((j & k >>1) == 0 && (k & j >> 1) == 0) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + Integer.bitCount(j));
}
}
}
}
}
int ans = 0;
for (int i : dp[m]) {
ans = Math.max(i, ans);
}
return ans;
}
}
hints: java operator preceedence: 1) » 2)==, != 3)& 4)&& it’s different than that in C++. This problem can also be solved using biporiate graph, will explain it later.
- Stickers to Spell Word
you can choose stickers (any one for any times) and form a target string from a subset of the chars. With dp intuition, we can form the status of the string with a int number(with target length of bits) to represent how the current string covers the chars of the target string, then from each reachable state, we transite to other states by iterating these candidate stickers(for one sticker we use it exhuastively to cover up uncovered bit) and at the same time update the cost of the best(longest) potential next state.
transition equation is: dp[next] = dp[cur] + 1 where next is the string that use one sticker to cover as many as uncoverd chars in cur compared to target, the sticker can be any sticker(because the quantity is limitedless)
class Solution {
public int minStickers(String[] stickers, String target) {
int len = target.length();
int n = 1 << len;
int dp[] = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
char[] tarr = target.toCharArray();
for (int st = 0; st < n; st++) {
//so far we have 0..0..1...1
if (dp[st] == Integer.MAX_VALUE) continue;
for (String s : stickers){
int next = st;
for (char ch : s.toCharArray()) {
for (int i = 0; i < len; i++) {
if ((next >> i & 1) == 0 && tarr[i] == ch) {
next = next | (1 << i);
break;
}
}
}
dp[next] = Math.min(dp[next], dp[st] + 1);
}
}
return dp[n-1] == Integer.MAX_VALUE ? -1 : dp[n-1];
}
}
Leave a Comment