DP with Bitmasking

Nishant Rana
Last Updated: May 13, 2022

Introduction

The first thing we need to make sure of before solving any DP with Bitmasking problem is that the constraints must be small because this approach takes exponential time and space.

Let us now discuss what is a Bitmask. 
Bitmask is a Binary Number that stores some value inside it. Generally, we use Bitmask to memoize a recursive solution that represents the things we have already considered or visited. 

Let us understand this with an example of the problem we will discuss further.

There is a salesman who wants to visit all the N cities once. Here the bitmask will be a Binary number and it will represent how many cities we have already visited when we are at a particular recursive call. The ith bit number which is set to 1 will represent that we have visited the ith city.
We maintain this Bitmask value and using this Bitmask value we try to memoize our recursive code.

Now, let us discuss the TSP problem.

We are given a 2-D array of characters, including ‘*’, ‘.’, and ‘#’.
*’ represents the Houses.
.’ represents an empty road.
#’ represents a blocked road.

We are currently at (0, 0) index and we need to visit all the houses only once and return back to our initial position (0, 0) at the end of the journey. We need to find the minimum distance to visit all the houses.

Approach

Our first step will be to calculate the shortest distance between the two houses. For this, we will run BFS from each house and find its minimum distance from each cell considering it as the source cell.

We will store the above result in a table of size O(Grid_size * N) (where ‘N’ is the number of houses) so that we don’t need to calculate it each time.

Now, we will try out all the combinations of traveling the houses and determine the minimum distance between them. 
We will be using DP with Bitmasking to store the result for different states to reuse them.

Let us define the DP with Bitmasking state for the same.
DP[index][mask]: It will represent the minimum distance covered to reach the (index)th house after traveling all the houses stored in the mask. All the bits which are set to 1 in the mask are visited by us in the current state.

As soon as the mask has all the bits set to 1((1 << N) - 1), that means we have visited all the cities and it is our answer.

At any state (index, mask), if all the bits are not set in the mask, we will visit the next house which is not already visited.

Hence the transition of DP with Bitmasking would look like as follows:

for(nxtHouse : off_bits_in_mask){
    Dp[index][mask] = min(dp[index][mask], dp[nxtHouse][mask.set_bit(nxtHouse)] + dist[index][nxtHouse]);
}

Refer to the below implementation of the above approach.

#include <bits/stdc++.h>
using namespace std;
 
#define INF 99999999
#define MAXR 12
#define MAXC 12
#define MAXMASK 2048
#define MAXHOUSE 12
 
/*
  It will store the 
  distance of each house
  from each cell
*/
int dist[MAXR][MAXC][MAXHOUSE];
 
// Memoization for dp with bitmasking states
int dp[MAXHOUSE][MAXMASK];
 
/*
  It will store 
  the index of 
  all the houses
*/
vector < pair < intint > > houses;
 
// Directions
int X[] = {-1001};
int Y[] = {01-10};
 
char arr[21][21];
 
/*
  len : number of houses + 1
  limit : 2 ^ len -1
  r, c : number of rows and columns
*/
int len, limit, r, c;
 
 
/*
  This function returns
  true if current cell is
  safe to visit else false.
*/
bool safe(int x, int y)
{
    if (x >= r or y>= c or x<0 or y<0)
      return false;
    if (arr[x][y] == '#')
      return false;
    return true;
}
 
 
/*
  This function runs the BFS from
  the idx house and finds its
  minimum distance from each cell.
*/
void getDist(int idx){
 
    // visited array to track visited cells
    bool vis[21][21];
    memset(vis, falsesizeof(vis));
 
    // getting current position
    int cx = houses[idx].first;
    int cy = houses[idx].second;
 
    // initializing queue for bfs
    queue < pair < intint > > pq;
    pq.push({cx, cy});
 
    /*
      Initializing the dist
      array to Infinity
    */
    for (int i = 0;i<= r;i++)
        for (int j = 0;j<= c;j++)
            dist[i][j][idx] = INF;
 
    // base conditions
    vis[cx][cy] = true;
    dist[cx][cy][idx] = 0;
 
    while (! pq.empty())
    {
        auto x = pq.front();
        pq.pop();
        for (int i = 0;i<4;i++)
        {
          cx = x.first + X[i];
          cy = x.second + Y[i];
          if (safe(cx, cy))
          {
              if (vis[cx][cy])
                  continue;
              vis[cx][cy] = true;
              dist[cx][cy][idx] = dist[x.first][x.second][idx] + 1;
              pq.push({cx, cy});
            }
        }
    }
}
 
int solve(int idx, int mask)
{


    // goal state
    if (mask == limit)
      return dist[0][0][idx];
 
    // if already visited state
    if (dp[idx][mask] != -1)
      return dp[idx][mask];
 
    int ret = INT_MAX;
 
    // state transition relation
    for (int i = 0;i<len;i++)
    {
        if ((mask & (1<<i)) == 0)
        {
            int newMask = mask | (1<<i);
            ret = min( ret, solve(i, newMask)
                + dist[houses[i].first][houses[i].second][idx]);
        }
    }
 
    // adding memoization and returning
    return dp[idx][mask] = ret;
}
 
void init()
{
    // initializing containers
    memset(dp, -1sizeof(dp));
    houses.clear();
 
    // populating houses tile positions
    for (int i = 0;i<r;i++)
        for (int j = 0;j<c;j++)
        {
            if (arr[i][j] == '*')
              houses.push_back({i, j});
        }
 
    houses.insert(houses.begin(), {00});
 
    len = houses.size();
 
    // calculating LIMIT_MASK
    limit = (1<<len) - 1;
 
    /*
      pre calculating distances 
      from all houses tiles to 
      each cell in the grid
    */
    for (int i = 0;i<len;i++)
      getDist(i);
}
 
int main(int argc, char const *argv[])
{
 
char A[4][7] = {    {'.''.''.''.''.''*''.'},
                    {'.''.''.''#''.''.''.'},
                    {'.''*''.''#''.''*''.'},
                    {'.''.''.''.''.''.''.'}
                };
 
    r = 4; c = 7;
 
    cout << "The given grid : " << endl;
 
    for (int i = 0;i<r;i++)
    {
        for (int j = 0;j<c;j++)
        {
            cout << A[i][j] << " ";
            arr[i][j] = A[i][j];
        }
        cout << endl;
    }

    init();
 
    int ans = solve(01);
 
    cout << "Minimum distance for the given grid : ";
    cout << ans << endl;
    return 0;
}

Output


Time Complexity: There will be a maximum of N * (2 ^ N) states and for each state, we will be traversing all the N houses. Hence, the overall time complexity will be O(N ^ 2 * 2 ^ N).

Space Complexity: We are maintaining a DP table of size (N * 2 ^ N) which is a dominating term. Hence, the Space Complexity is O(N * 2^N).

FAQs

  1. What is the Time and Space complexity of the approach used?
    Time Complexity: There will be a maximum of N * (2 ^ N) states and for each state, we will be traversing all the N houses. Hence, the overall time complexity will be O((N ^ 2) * 2 ^ N).
    Space Complexity: We are maintaining a DP table of size (N * (2 ^ N)) which is a dominating term. Hence, the Space Complexity is O(N * (2 ^ N)).
     
  2. What does dp[index][mask] represent?
    It will represent the minimum distance covered to reach the (index)th house after traveling all the houses stored in the mask. All the bits which are set to 1 in the mask are visited by us in the current state.

Key Takeaways

In this blog, we have covered the following things:

  1. We first discussed the DP with Bitmasking approach to solve this problem.
  2. Then we discussed the code, time, and space complexity of the approach used.

If you want to learn more about DP with Bitmasking and want to practice some questions which require you to take your basic knowledge on Dynamic Programming a notch higher, then you can visit our Guided Path for Dynamic Programming

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
1 upvote