Maximum Students Taking Exam LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[8][(1 << 8) - 1];
4
  int maxStudents(vector<vector<char>> &seats) {
5
    memset(dp, -1, sizeof(dp));
6
    return helper(seats, 0, 0);
7
  }
8
  int helper(vector<vector<char>> &seats, int prevAllocation, int idx) {
9
    if (idx == seats.size()) return 0;
10
    int sz = seats[0].size(), masks = ((1 << sz) - 1), maxi = 0;
11
    // masks is for iterating over all subsets
12
    if (dp[idx][prevAllocation] != -1) return dp[idx][prevAllocation];
13
    while (masks >= 0) {
14
      int curAllocation = 0, cnt = 0;
15
      for (int i = 0; i < sz; i++) {
16
        if (seats[idx][i] != '#' && masks >> i & 1) {
17
          int ul = i - 1, ur = i + 1;
18
          bool canPlace = true;
19
          if (ul >= 0)
20
            if (prevAllocation >> ul & 1 || curAllocation >> ul & 1) canPlace = false;
21
          if (ur < sz)
22
            if (prevAllocation >> ur & 1 || curAllocation >> ur & 1) canPlace = false;
23
          if (canPlace) {
24
            curAllocation |= 1 << i;
25
            cnt++;
26
          }
27
        }
28
      }
29
      maxi = max(maxi, cnt + helper(seats, curAllocation, idx + 1));
30
      masks--;
31
    }
32
    dp[idx][prevAllocation] = maxi;
33
    return maxi;
34
  }
35
};