鏈接：https://leetcode-cn.com/problems/maximum-students-taking-exam
思路:
1. 狀態(tài)壓縮
在m行n列seats中，對于每一行，每把椅子可分為坐人（狀態(tài)1）和不坐人（狀態(tài)0）兩種狀態(tài)。在先不考慮學生坐法是否滿足題目要求的前提下，每行共有2^n種狀態(tài)。1 <= n <= 8，這在暗示我們可以用狀態(tài)壓縮。如狀態(tài)state=100010表示第0和第4把椅子坐人。
2. 合法性檢查
(1) 保證學生沒有坐在壞的椅子上。我們把椅子的好壞狀態(tài)用chair記錄，好椅子"."記為0可以坐人，壞椅子"#"記為1不可以坐人。如椅子"#.##.#"可表示為101101。我們只需將椅子的好壞狀態(tài)，與學生狀態(tài)進行按位與操作，保證chair&state==0即可。
(2) 檢查學生左右兩側(cè)是否有人。我們將狀態(tài)state分別左移，右移一位，并與該狀態(tài)進行按位與操作，即檢查state&(state<<1)==0 and state&(state>>1)==0即可。
(3) 檢查學生左上右上兩側(cè)是否有人。我們將上一行的狀態(tài)last_state左移一位，右移一位和這行狀態(tài)state進行按位與操作，即檢查state&(last_state<<1)==0 and state&(state>>1)==0即可。
3. 狀態(tài)轉(zhuǎn)移方程
dp[row][state] = max(dp[row-1][last_state]) + state.count(1)，其中state.count(1)表示該狀態(tài)state坐人的數(shù)量。
代碼：
1. 帶狀態(tài)壓縮的動態(tài)規(guī)劃算法
自底向上，時間復雜度：，空間復雜度：
。
我們可以先把合法狀態(tài)保存下來，但是最壞情況下，沒有壞的椅子，只需保證左右兩側(cè)沒有人，不需要考慮椅子好壞情況，合法狀態(tài)仍然 。
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
# 遇到.時進行與運算結(jié)果為0，表示可以坐人
# 如狀態(tài)010010，與101101進行與操作，即010010&101101=0，表示該狀態(tài)合法，學生沒有坐在壞的椅子上
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): # 遍歷本行所有合法狀態(tài)
if state & chair[row] == 0 and state & (state << 1) == 0 and state & (state >> 1) == 0:
for last_state in range(1 << n): # 遍歷上一行所有合法狀態(tài)
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): # 遍歷下一行所有合法狀態(tài)
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)]
# 記錄以某一行某個狀態(tài)下為根的子樹的最大學生數(shù)
# 如memo[2][100001]代表第2行狀態(tài)下100001，第2行（包含）到第m行的最大學生數(shù)
memo = [{} for _ in range(m + 1)]
return backtraceWithMemo(row=0, state=0)
本題還可作為二分圖的最大獨立集算法，詳情參照參考鏈接。
參考鏈接：
