LeetCode 1349. 参加考试的最大学生数,状压DP
一、题目
1、题目描述
给你一个?
m?* n
?的矩阵?seats
?表示教室中的座位分布。如果座位是坏的(不可用),就用?'#'
?表示;否则,用?'.'
?表示。学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的?最大?学生人数。
学生必须坐在状况良好的座位上。
2、接口描述
class Solution {
public:
int maxStudents(vector<vector<char>>& seats) {
}
};
3、原题链接
二、解题报告
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][1<<8] , 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(vector<vector<char>>& 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][1<<8] , valid[8];
int maxStudents(vector<vector<char>>& 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]];
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!