Maximum Students Taking Exam LeetCode solution in Java

1
class Solution {
2
  private Integer[][] f;
3
  private int n;
4
  private int[] ss;
5

6
  public int maxStudents(char[][] seats) {
7
    int m = seats.length;
8
    n = seats[0].length;
9
    ss = new int[m];
10
    f = new Integer[1 << n][m];
11
    for (int i = 0; i < m; ++i) {
12
      for (int j = 0; j < n; ++j) {
13
        if (seats[i][j] == '.') {
14
          ss[i] |= 1 << j;
15
        }
16
      }
17
    }
18
    return dfs(ss[0], 0);
19
  }
20

21
  private int dfs(int seat, int i) {
22
    if (f[seat][i] != null) {
23
      return f[seat][i];
24
    }
25
    int ans = 0;
26
    for (int mask = 0; mask < 1 << n; ++mask) {
27
      if ((seat | mask) != seat || (mask & (mask << 1)) != 0) {
28
        continue;
29
      }
30
      int cnt = Integer.bitCount(mask);
31
      if (i == ss.length - 1) {
32
        ans = Math.max(ans, cnt);
33
      } else {
34
        int nxt = ss[i + 1];
35
        nxt &= ~(mask << 1);
36
        nxt &= ~(mask >> 1);
37
        ans = Math.max(ans, cnt + dfs(nxt, i + 1));
38
      }
39
    }
40
    return f[seat][i] = ans;
41
  }
42
}