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]);
}
};
