LC.P1349[参加考试的最大学生数]

方法一：记忆化搜索+状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    int[][] cache;

    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length;
        int[] a = new int[m]; // a[i] 是第 i 排可用椅子的下标集合
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (seats[i][j] == '.') {
                    a[i] |= 1 << j;
                }
            }
        }
        cache = new int[m][1 << n];
        for (int[] row : cache) {
            Arrays.fill(row, -1);
        }
        return dfs(m - 1, a[m - 1], a);
    }

    private int dfs(int i, int j, int[] a) {
        if (cache[i][j] != -1) return cache[i][j];
        if (i == 0) {
            if (j == 0) {
                return 0;
            }
            int lb = j & -j;
            return cache[i][j] = dfs(i, j & ~(lb * 3), a) + 1;
        }
        int ans = dfs(i - 1, a[i - 1], a); // 第 i 排空着
        for (int s = j; s > 0; s = (s - 1) & j) { // 枚举 j 的子集 s
            if ((s & (s >> 1)) == 0) { // s 没有连续的 1
                int t = a[i - 1] & ~(s << 1 | s >> 1); // 去掉不能坐人的位置
                ans = Math.max(ans, dfs(i - 1, t, a) + Integer.bitCount(s));
            }
        }
        return cache[i][j] = ans;
    }
}
  • 时间复杂度：$O(m \times 3^n)$
  • 空间复杂度：$O(m \times 2^n)$