LeetCode 每日一题 Day 24(Hard) ||dp动态规划

1349. 参加考试的最大学生数

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

这题实在是不会，读者可以看看灵神的题解：教你一步步思考动态规划：从记忆化搜索到递推

题解代码如下：

class Solution {
public:
    int maxStudents(vector<vector<char>> &seats) {
        int m = seats.size(), n = seats[0].size();
        vector<int> a(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;
                }
            }
        }

        vector<vector<int>> memo(m, vector<int>(1 << n, -1)); // -1 表示没有计算过
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            int &res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            if (i == 0) {
                if (j == 0) {
                    return res = 0;
                }
                int lb = j & -j;
                return res = dfs(i, j & ~(lb * 3)) + 1;
            }
            res = dfs(i - 1, a[i - 1]); // 第 i 排空着
            for (int s = j; s; s = (s - 1) & j) { // 枚举 j 的子集 s
                if ((s & (s >> 1)) == 0) { // s 没有连续的 1
                    int t = a[i - 1] & ~(s << 1 | s >> 1); // 去掉不能坐人的位置
                    res = max(res, dfs(i - 1, t) + __builtin_popcount(s));
                }
            }
            return res;
        };
        return dfs(m - 1, a[m - 1]);
    }
};