Bitmask/State Compression DP
5 min readJun 20, 2020
Usually, the state of DP can use limited variables to represent such as dp[i], dp[i][j], dp[i][j][k]. However, sometimes, the states of a DP problem may contain multiple statuses. In this case, we can think about using the state compression approaches to represent the DP state. For example, if we have a grid, and we want to represent the presence of elements in each row of the board, we can use a N bits number to represent all possible states. Each bit contains two values: 0 or 1. 0 means absent and 1 means exist.
Related problems
1125. Smallest Sufficient Team
class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
proj = {req_skills[i]:i for i in range(len(req_skills))}
dp = {'0'*len(req_skills):[]}
for i,skills in enumerate(people):
for skill_set in list(dp.keys()):
new_set = str(skill_set)
for skill in skills:
if skill in proj:
new_set = new_set[:proj[skill]] + '1' +new_set[proj[skill]+1:]
if new_set not in dp or len(dp[new_set]) > len(dp[skill_set]) + 1:
dp[new_set] = [val for val in dp[skill_set]] + [i]
return dp['1'*len(req_skills)]lee215’s code is more efficient
class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
n, m = len(req_skills), len(people)
key = {v: i for i, v in enumerate(req_skills)}
dp = {0: []}
for i, p in enumerate(people):
his_skill = 0
for skill in p:
if skill in key:
his_skill |= 1 << key[skill]
for skill_set, need in list(dp.items()):
with_him = skill_set | his_skill
if with_him == skill_set: continue
if with_him not in dp or len(dp[with_him]) > len(need) + 1:
dp[with_him] = need + [i]
return dp[(1 << n) - 1]943. Find the Shortest Superstring
see [4]
Solution mentioned here
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
vector<int> pre(n); // pre[i]: the bit representation of all dependencies of course i
for(auto& e : dependencies){
e[0] -= 1;
e[1] -= 1;
pre[e[1]] |= 1 << e[0];
}
// i is the bit representation of a combination of courses.
// dp[i] is the minimum days to complete all the courses
vector<int> dp(1 << n, n);
// no need time to finish 0 courses
dp[0] = 0;
for(int i = 0; i < (1 << n); i += 1){
int ex = 0;
// find out ex, the bit representation of the all courses that we can study now.
// since we have i and pre[j], we know course j can be studied if i contains all it's prerequisites ((i & pre[j]) == pre[j])
for(int j = 0; j < n; j += 1) if((i & pre[j]) == pre[j]) ex |= 1 << j;
// we don't want to study anything from what we have already studied (i represents set of courses that we have studied)
ex &= ~i;
// enumerate all the bit 1 combinations of ex
// this is a typical method to enumerate all subsets of a bit representation:
// for (int i = s; i; i = (i - 1) &ｓ)
// __builtin_popcount counts bits == 1
for(int s = ex; s; s = (s - 1) & ex) if(__builtin_popcount(s) <= k){
// any combination of courses (if less or equal than k) could be studied at this step
// i | s means what we combine already studied courses before with courses we can study at the current step
dp[i | s] = min(dp[i | s], dp[i] + 1);
}
}
// dp.back is the state when we studied all the courses. e.g. 11111...
return dp.back();
}
};Solution from Here
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
// dependency[i]: dependency mask of course i, the set bits is dependent
vector<int> dependency(n, 0);
for (size_t i = 0; i < dependencies.size(); ++i) {
int course = dependencies[i][1] - 1;
int prerequisite = dependencies[i][0] - 1;
dependency[course] |= 1 << prerequisite;
}
// prerequisites[i]: prerequisites mask of mask i, the set bits is prerequisites
vector<int> prerequisites(1 << n, 0);
// iterate all mask and generate prerequisites mask of each mask
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
prerequisites[i] |= dependency[j];
}
}
}
// dp[i]: minimum number of semesters of mask i, the set bits are courses that have not been taken
vector<int> dp(1 << n, n + 1);
dp[0] = 0;
for (int i = 1; i < (1 << n); ++i) {
// iterate all submask of mask i, and this mask is the mask of last semester
// see: https://cp-algorithms.com/algebra/all-submasks.html
for (int j = i; j; j = (j - 1) & i) {
if (count_setbit(j) > k) {
continue;
}
int already_taken = i ^ ((1 << n) - 1);
if ((already_taken & prerequisites[j]) == prerequisites[j]) {
dp[i] = min(dp[i], dp[i ^ j] + 1);
}
}
}
return dp[(1 << n) - 1];
}
private:
int count_setbit(int mask) {
if (mask == 0) {
return 0;
}
return 1 + count_setbit(mask & (mask - 1));
}
};Top rank submission
class Solution {
int a[15],f[32768],o[32768];
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
memset(a,0,sizeof(a));
int i,j,l;
for(auto e:dependencies)a[e[1]-1]|=1<<e[0]-1;
for(i=1;i<1<<n;i++)o[i]=o[i>>1]+(i&1);
memset(f,127,sizeof(f));
for(i=f[0]=0;i<1<<n;i++)if(f[i]<=n)
{
for(j=l=0;j<n;j++)if(!(i>>j&1)&&(a[j]&i)==a[j])l|=1<<j;
for(j=l;j;j=j-1&l)if(o[j]<=k)f[i|j]=min(f[i|j],f[i]+1);
}
return f[(1<<n)-1];
}
};A nice video about this problem can be found HERE.
Code based on the video explanation
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k)
{
vector<int> prerequisite(1<<n, 0);
vector<int> dp(1<<n, INT_MAX-1);
vector<int> prerequisite_per_course(n, 0);
dp[0] = 0;
for (auto &x:dependencies)
{
prerequisite_per_course[x[1]-1] |= 1<<(x[0]-1);
}
for (int state = 0; state < (1<<n); ++state)
{
for (int i=0;i<n;++i)
{
if(state>>i&1)prerequisite[state] |= prerequisite_per_course[i];
}
}
for (int state = 0; state < (1<<n); ++state)
{
//cout<<"state: "<<state<<endl;
//1 is good
for(int subset=state; subset>=0;subset=(subset-1)&state)
{
//2.each time can at most take K classes
//cout<<"subset: "<<subset<<endl;
if(__builtin_popcount(state)-__builtin_popcount(subset)<=k && (prerequisite[state]&subset) == prerequisite[state])
{
dp[state] = min(dp[state], dp[subset]+1);
}
if (subset==0)break;
}
}
return dp[(1<<n)-1];
}
};// bitmask to show the course
// 0000 --> 1111
// return is dp[1111]// state from 0 to 1111
// dp[state] = min( dp[subset] +1 for subset of state)// 1. subset is a subset of the current state
// 2. each time can at most take K classes
// 3. subset contains all the prerequisite of the current state.
Reference
[2]https://www.acwing.com/blog/content/174/
