DP with Bitmasking - Naukri Code 360

Q: 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)).

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 < int, int > > houses;

// Directions
int X[] = {-1, 0, 0, 1};
int Y[] = {0, 1, -1, 0};

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, false, sizeof(vis));

  // getting current position
  int cx = houses[idx].first;
  int cy = houses[idx].second;

  // initializing queue for bfs
  queue < pair < int, int > > 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, -1, sizeof(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(), {0, 0});

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(0, 1);

  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

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)).
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:

We first discussed the DP with Bitmasking approach to solve this problem.
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.

Check out this problem - Count Ways To Reach The Nth Stair

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