链接：https://leetcode-cn.com/problems/maximum-students-taking-exam
思路:
1. 状态压缩
在m行n列seats中，对于每一行，每把椅子可分为坐人（状态1）和不坐人（状态0）两种状态。在先不考虑学生坐法是否满足题目要求的前提下，每行共有2^n种状态。1 <= n <= 8，这在暗示我们可以用状态压缩。如状态state=100010表示第0和第4把椅子坐人。
2. 合法性检查
(1) 保证学生没有坐在坏的椅子上。我们把椅子的好坏状态用chair记录，好椅子"."记为0可以坐人，坏椅子"#"记为1不可以坐人。如椅子"#.##.#"可表示为101101。我们只需将椅子的好坏状态，与学生状态进行按位与操作，保证chair&state==0即可。
(2) 检查学生左右两侧是否有人。我们将状态state分别左移，右移一位，并与该状态进行按位与操作，即检查state&(state<<1)==0 and state&(state>>1)==0即可。
(3) 检查学生左上右上两侧是否有人。我们将上一行的状态last_state左移一位，右移一位和这行状态state进行按位与操作，即检查state&(last_state<<1)==0 and state&(state>>1)==0即可。
3. 状态转移方程
dp[row][state] = max(dp[row-1][last_state]) + state.count(1)，其中state.count(1)表示该状态state坐人的数量。
代码：
1. 带状态压缩的动态规划算法
自底向上，时间复杂度：，空间复杂度：
。
我们可以先把合法状态保存下来，但是最坏情况下，没有坏的椅子，只需保证左右两侧没有人，不需要考虑椅子好坏情况，合法状态仍然 。
from typing import List
from functools import reduce
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
# 将不可用的椅子设置为1，如'#.##.#'设置为101101，即为45
# 遇到.时进行与运算结果为0，表示可以坐人
# 如状态010010，与101101进行与操作，即010010&101101=0，表示该状态合法，学生没有坐在坏的椅子上
chair = [0] + [reduce(lambda x, y: x | 1 << y, [0] + [j for j in range(n) if seats[i][j] == '#']) for i in range(m)]
# print(chair) # 示例 1: [0, 45, 30, 45]
dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]
for row in range(1, m + 1):
for state in range(1 << n): # 遍历本行所有合法状态
if state & chair[row] == 0 and state & (state << 1) == 0 and state & (state >> 1) == 0:
for last_state in range(1 << n): # 遍历上一行所有合法状态
if state & (last_state << 1) == 0 and state & (last_state >> 1) == 0:
dp[row][state] = max(dp[row][state], dp[row - 1][last_state] + bin(state).count('1'))
return max(dp[m])
2. 带备忘录的回溯算法
自顶向下。
from typing import List
from functools import reduce
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
def backtraceWithMemo(row: int, state: int):
if state in memo[row]:
return memo[row][state]
if row == m:
return bin(state).count('1')
count = 0
for next_state in range(1 << n): # 遍历下一行所有合法状态
if next_state & chair[row + 1] == 0 and next_state & (next_state << 1) == 0 and next_state & (next_state >> 1) == 0:
if state & (next_state << 1) == 0 and state & (next_state >> 1) == 0:
memo[row + 1][next_state] = backtraceWithMemo(row + 1, next_state)
count = max(count, memo[row + 1][next_state])
count += bin(state).count('1')
return count
m, n = len(seats), len(seats[0])
chair = [0] + [reduce(lambda x, y: x | 1 << y, [0] + [j for j in range(n) if seats[i][j] == '#']) for i in range(m)]
# 记录以某一行某个状态下为根的子树的最大学生数
# 如memo[2][100001]代表第2行状态下100001，第2行（包含）到第m行的最大学生数
memo = [{} for _ in range(m + 1)]
return backtraceWithMemo(row=0, state=0)
本题还可作为二分图的最大独立集算法，详情参照参考链接。
参考链接：
