江苏省执业建设注册中心网站,大型免费网站制作,住房和城乡建设网站,北京设计制作网站制作一、题目
1、题目描述 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的#xff08;不可用#xff09;#xff0c;就用 # 表示#xff1b;否则#xff0c;用 . 表示。 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷#xff0c;但…一、题目
1、题目描述 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的不可用就用 # 表示否则用 . 表示。 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。 学生必须坐在状况良好的座位上。 2、接口描述
class Solution {
public:int maxStudents(vectorvectorchar seats) {}
}; 3、原题链接
1349. 参加考试的最大学生数 二、解题报告
1、思路分析
对于这种网格图上的合法位置问题很容易联想到状压DP。
根据题目规则按行考虑每一行的有效状态和当前行有关也跟上一行有关
状态设计
每一行的状态可以用一个二进制数字来保存1代表有学生0代表没有那么我们定义f[i][j]为下标i行状态为j时最大学生数目
那么递推关系是怎样的呢
状态转移
首先对于状态j而言它必须是一个合法状态他要满足当前行合法即j (j 1) 0即无相邻1
那么对于上一行状态不妨设为t那么t (j 1 | j 1) 0我们有递推公式
f[i][j] max(f[i][j] , f[i - 1][t] num[j])其中num[j]为状态j中1的个数
有了递推公式之后其实还是有许多细节要处理的
预处理
根据传入参数我们可以预处理出每行的座位状态仍然是1代表有0代表无由于每行的有效状态是要从这个座位状态的子集里面挑的座位状态可以用来枚举子集
状态初始化
我们可以初始化出第0行的所有状态下的最大学生数目为社么呢
对于第0行初始化显然问题就简化为了一行位置有若干位置可以坐人要求不能两两相邻求最大数目我们直接贪心的取即可从第一个空位置开始取如果相邻也是空位置就跳过去具体代码就是 for(int i 1 ; i (1 n) ; i) { int lb i-i; f[0][i] f[0][i ~(lb * 3)] 1; } 2、复杂度 时间复杂度O(m*3^n) 空间复杂度O(m*2^n) 3、代码详解
记忆化搜索版本
class Solution {
public:
int f[8][18] , valid[8];int dfs(int x , int y){int res f[x][y];if(~res) return res;if(!x){if(!y) return res 0;int lb y-y;return res dfs(x , (y ~(lb*3))) 1;}res dfs(x - 1 , valid[x - 1]);for(int i y ; i ; i (i - 1) y){if(!(i (i 1))){int t valid[x - 1] ~((i 1) | (i 1));res max(res , dfs(x - 1, t) __builtin_popcount(i));}}return res;}int maxStudents(vectorvectorchar seats) {int m seats.size() , n seats[0].size();memset(f , -1 , sizeof(f));memset(valid , 0 , sizeof(valid));for(int i 0 ; i m ; i)for(int j 0 ; j n ; j)if(seats[i][j] .) valid[i] | (1 j);return dfs(m - 1 , valid[m - 1]);}
};
递推版本
class Solution {
public:
int f[8][18] , valid[8];int maxStudents(vectorvectorchar seats) {int m seats.size() , n seats[0].size();memset(f , 0 , sizeof(f));memset(valid , 0 , sizeof(valid));for(int i 0 ; i m ; i)for(int j 0 ; j n ; j)if(seats[i][j] .) valid[i] | (1 j);for(int i 1 ; i (1 n) ; i){int lb i-i;f[0][i] f[0][i ~(lb * 3)] 1;}for(int i 1 ; i m ; i){for(int j valid[i] ; j ; j (j - 1) valid[i]){f[i][j] f[i - 1][valid[i - 1]];for(int k j ; k ; k (k - 1) j){if(!(k (k 1))){int t valid[i - 1] ~(k 1 | k 1);f[i][j] max(f[i][j] , f[i - 1][t] f[0][k]);}}}f[i][0] f[i - 1][valid[i - 1]];}return f[m - 1][valid[m - 1]];}
};
