LeetCode 1349. 参加考试的最大学生数：状态压缩 + 记忆化搜索

【LetMeFly】1349.参加考试的最大学生数：状态压缩 + 记忆化搜索

力扣题目链接：https://leetcode.cn/problems/maximum-students-taking-exam/

给你一个?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

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

写一个函数dfs(row, status)，用来计算第row行的“坐人情况的二进制串”为status的情况下，前row行最多坐多少人。

如果我们实现了这个函数，那么直接返回最后一行 1 << n个状态的dfs最大值即为答案。所以这个函数怎么实现呢？

1. 首先判断status的合法性：不能坐在坏座位上、不能两个人挨着坐。
2. 当前状态下的最大值，等于上一行所有状态（不用特别考虑上一行是否是合法状态，因为若不合法则dfs会返回极小值）下的最大值，加上这一行当前状态下的人数
3. 在第2步的“上一行状态”中，需要满足：上一行和这一行没有“斜对面”关系

• 时间复杂度$O(mn\times 2^{2n})$，其中$seats$为$m$行$n$列。状态数共有$m\times 2^n$种（dfs的参数），计算一个状态复杂度$n\times 2^n$
• 空间复杂度$O(m\times 2^n)$

AC代码

C++

class Solution {
private:
    int m, n;
    vector<vector<char>> seats;
    unordered_map<int, int> visited;

    bool isOkState(int row, int status) {
        // return true;
        for (int j = 0; j < n; j++) {
            if (!(status & (1 << j))) {
                continue;
            }
            // 二进制状态下这一位为1
            if (seats[row][j] == '#') {
                return false;
            }
            if (j > 0 && (status & (1 << (j - 1)))) {  // 相邻两个1
                return false;
            }
        }
        return true;
    }

    int dfs(int row, int status) {
        if (visited.count((row << n) + status)) {
            return visited[(row << n) + status];
        }
        if (!isOkState(row, status)) {
            return -1000;
        }
        int cnt1 = __builtin_popcount(status);
        if (!row) {
            return cnt1;
        }
        int ans = 0;
        for (int lastStatus = 0; lastStatus < (1 << n); lastStatus++) {
            for (int j = 0; j < n; j++) {
                if (j > 0 && (status & (1 << j)) && (lastStatus & (1 << (j - 1)))) {
                    goto loop;
                }
                if (j + 1 < n && (status & (1 << j)) && (lastStatus & (1 << (j + 1)))) {
                    goto loop;
                }
            }
            ans = max(ans, dfs(row - 1, lastStatus));
            loop:;
        }
        ans += cnt1;
        return visited[(row << n) + status] = ans;
    }
public:
    int maxStudents(vector<vector<char>>& seats) {
        this->seats = move(seats);
        m = this->seats.size(), n = this->seats[0].size();
        int ans = 0;
        for (int j = 0; j < (1 << n); j++) {
            ans = max(ans, dfs(m - 1, j));
        }
        return ans;
    }
};

Python

# from typing import List
# from functools import cache

class Solution:
    @cache
    def dfs(self, row: int, status: int) -> int:
        for j in range(self.n):
            if not status & (1 << j):
                continue
            if self.seats[row][j] == '#':  # 坏椅子坐人
                return -1000
            if j > 0 and status & (1 << (j - 1)):  # 连续两人
                return -1000
        cnt1 = bin(status).count('1')
        if not row:
            return cnt1
        lastRowMax = 0
        for lastStatus in range(1 << self.n):
            ok = True
            for j in range(self.n):
                if j > 0 and status & (1 << j) and lastStatus & (1 << (j - 1)):
                    ok = False
                    break
                if j + 1 < self.n and status & (1 << j) and lastStatus & (1 << (j + 1)):
                    ok = False
                    break
            if ok:
                lastRowMax = max(lastRowMax, self.dfs(row - 1, lastStatus))
        return cnt1 + lastRowMax
    
    def maxStudents(self, seats: List[List[str]]) -> int:
        self.seats = seats
        self.m, self.n = len(seats), len(seats[0])
        ans = 0
        for status in range(1 << self.n):
            ans = max(ans, self.dfs(self.m - 1, status))
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135217045