What is the key pattern in Maximum Students Taking Exam?

The problem is a classic state transition dynamic programming with bitmasking where each row's configuration depends on the previous row to prevent cheating.

How do I represent row states efficiently?

Use bitmask integers to encode occupied seats, allowing O(1) checks for adjacency and diagonal conflicts.

Can this approach handle broken seats?

Yes, generate only valid row states where students are placed on non-broken seats, automatically excluding '#' positions.

What is the time complexity for m x n seats?

Time complexity is roughly O(m * 2^n * 2^n) since all valid row states and transitions between rows are considered.

How does GhostInterview handle cheating detection?

It uses DP with bitmasking to prevent placing students in positions where they can see each other's answers diagonally or adjacent in the same row.

#1349

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

参加考试的最大学生数

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊…

数组动态规划位运算矩阵位掩码

题目描述

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的最大学生人数。

学生必须坐在状况良好的座位上。

示例 1：

输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

示例 2：

输入：seats = [[".","#"],
              ["#","#"],
              ["#","."],
              ["#","#"],
              [".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。

示例 3：

输入：seats = [["#",".",".",".","#"],
              [".","#",".","#","."],
              [".",".","#",".","."],
              [".","#",".","#","."],
              ["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。

提示：

seats 只包含字符 '.' 和'#'
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

lightbulb

解题思路

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

我们注意到，每个座位有两种状态：可选和不可选。因此，我们可以使用二进制数来表示每一行的座位状态，其中 $1$ 表示可选，而 $0$ 表示不可选。例如，对于示例 $1$ 中的第一行，我们可以表示为 $010010$ 。因此，我们将初始座位转换为一个一维数组 $ss$ ，其中 $ss[i]$ 表示第 $i$ 行的座位状态。

接下来，我们设计一个函数 $dfs(seat, i)$ ，表示从第 $i$ 行开始，当前行的座位状态为 $seat$ ，可以容纳的最多学生人数。

我们可以枚举第 $i$ 行的所有选座状态 $mask$ ，并且判断 $mask$ 是否满足以下条件：

状态 $mask$ 不能选择 $seat$ 之外的座位；
状态 $mask$ 不能选择相邻的座位。

如果满足条件，我们求出当前行选择的座位个数 $cnt$ ，如果当前是最后一行，则更新函数的返回值，即 $ans = \max(ans, cnt)$ 。否则，我们继续递归地求解下一行的最大人数，下一行的座位状态 $nxt = ss[i + 1]$ ，并且需要排除当前行已选座位的左右两侧。然后我们递归地求解下一行的最大人数，即 $ans = \max(ans, cnt + dfs(nxt, i + 1))$ 。

最后，我们将 $ans$ 作为函数的返回值返回。

为了避免重复计算，我们可以使用记忆化搜索，将函数 $dfs(seat, i)$ 的返回值保存在一个二维数组 $f$ 中，其中 $f[seat][i]$ 表示从第 $i$ 行开始，当前行的座位状态为 $seat$ ，可以容纳的最多学生人数。

时间复杂度 $O(4^n \times n \times m)$ ，空间复杂度 $O(2^n \times m)$ 。其中 $m$ 和 $n$ 分别为座位的行数和列数。

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

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        def f(seat: List[str]) -> int:
            mask = 0
            for i, c in enumerate(seat):
                if c == '.':
                    mask |= 1 << i
            return mask

        @cache
        def dfs(seat: int, i: int) -> int:
            ans = 0
            for mask in range(1 << n):
                if (seat | mask) != seat or (mask & (mask << 1)):
                    continue
                cnt = mask.bit_count()
                if i == len(ss) - 1:
                    ans = max(ans, cnt)
                else:
                    nxt = ss[i + 1]
                    nxt &= ~(mask << 1)
                    nxt &= ~(mask >> 1)
                    ans = max(ans, cnt + dfs(nxt, i + 1))
            return ans

        n = len(seats[0])
        ss = [f(s) for s in seats]
        return dfs(ss[0], 0)

speed

复杂度分析

指标	值
时间	complexity is O(m * 2^n * 2^n) due to enumerating all valid row states and transitions. Space complexity is O(2^n) for storing DP values per row. Both depend heavily on n, but m is small (<=8).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize this as a state transition DP problem with bitmasking for seating constraints?
question_mark
Can you generate all valid seating configurations per row efficiently without checking every permutation?
question_mark
How would you ensure students in the current row do not see students diagonally in the previous row?

warning

常见陷阱

外企场景

error
Failing to enforce that students in the current row cannot see upper-left or upper-right neighbors in the previous row.
error
Not filtering out row configurations that place students in broken seats.
error
Incorrectly counting adjacent students in the same row which violates the no-cheating rule.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize students while also minimizing empty seats between them for social distancing enforcement.
arrow_right_alt
Allow only one type of diagonal visibility and compute the new maximum seating arrangement.
arrow_right_alt
Extend the classroom to 3D (multiple floors) while maintaining visibility constraints per floor.

help

常见问题

外企场景

继续练习

#1255 得分最高的单词集合 #996 平方数组的数目 #943 最短超级串