leetcode.1349. 参加考试的最大学生数(状压dp)

$Description$
图片说明

$Solution$
状态压缩 $dp$ 。将每一行的学生的状态看作 $j$ , $dp[i][j]$ 表示第 $i$ 行状态为 $j$ 时前 $i$ 行的最大学生数量。
状态转移方程： $dp[i][j]=max(dp[i][j],dp[i-1][k]+num(j))$ 。 $num(j)为j的二进制1的个数$ 。

$Code$

class Solution {
public:
    int maxStudents(vector<vector<char>>& a) {
        int m=a.size(),n=a[0].size();        
        int dp[10][1<<9]={0},ans=0;
        for(int j=0;j<(1<<n);j++)if(ok(a,0,j))dp[0][j]=__builtin_popcount(j);
        for(int i=1;i<m;i++){
            for(int j=0;j<(1<<n);j++){
                if(ok(a,i,j)){
                    for(int k=0;k<(1<<n);k++){
                        if(!(j<<1&k)&&!(j>>1&k))//判断状态j的学生是否可以看到状态k的学生
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+__builtin_popcount(j));
                    }
                }
                ans=max(ans,dp[i][j]);
            }
        }
        return ans;
    }
    bool ok(vector<vector<char>>& a,int p,int j){//判断是否合法状态
        int n=a[0].size();
        for(int i=1;i<n;i++){
            if((j>>i&1)&&(j>>(i-1)&1))return 0;
        }
        for(int i=0;i<n;i++){
            if(j>>i&1){
                if(a[p][i]=='#')return 0;
            }
        }
        return 1;
    }
};