# 1349. Maximum Students Taking Exam
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-students-taking-exam/
## 思路
[1411. Number of Ways to Paint N × 3 Grid](https://hackmd.io/AKffexhVRtGqAo1_PAqr2Q)的变式
每一排的排法只依赖上一排的排法 所以是一个基本型I时间序列
我们设计```dp[i][s]```表示将第```i```行安排成状态```s```时，前```i```行最多能安排多少人。```s```是一个8bit的整型数字就足以代表每一个行的策略（每个bit表示该位置是否坐人），范围就是[0,255]。对于```dp[i][s]```，我们只需要遍历所有的```dp[i-1][t]```（表示第```i-1```行安排成状态```t```的策略），查看```s```本身是否合法，以及策略```s```能否接在策略```t```后面。都满足的话，那么```dp[i][s]```及可以更新为```dp[i-1][t]+count(s)```，其中```count(s)```表示第```i```行安排策略```s```所对应的该行的人数。
## Code

class Solution {
    int n;
    public int maxStudents(char[][] seats) {
        int m = seats.length;
        n = seats[0].length;
        int[][] dp = new int[m][1<<n];
        
        // the first row of dp
        for(int state=0; state<(1<<n); state++){
            if(selfCheck(state, seats, 0)){
                dp[0][state] = count(state);
            }
        }
        //other rows of dp
        for(int i=1; i<m; i++){
            for(int state=0; state<(1<<n); state++){
                if(selfCheck(state, seats, i)){
                    int cnt = count(state);
                    for(int prev=0; prev<(1<<n); prev++){
                        if(selfCheck(prev, seats, i-1) && checkDiffRows(state, prev)){
                            dp[i][state] = Math.max(dp[i][state], dp[i-1][prev]+cnt);
                        }
                    }
                }
            }
        }
        
        //get answer
        int ans = 0;
        for(int state=0; state<(1<<n); state++){
            ans = Math.max(ans, dp[m-1][state]);
        }
        return ans;
    }
    private int count(int mask){
        int ans=0;
        for(int i=0; i<n; i++){
            if(((mask>>i)&1)==1) ans++;
        }
        return ans;
    }
    private boolean selfCheck(int mask, char[][] seats, int row){
        List<Integer> students = new ArrayList<>();
        for(int i=0; i<n; i++){
            if(((mask>>i)&1)==1) students.add(i);
        }
        for(int i=0; i<students.size(); i++){
            if(i!=0 && students.get(i)-students.get(i-1)==1) return false;
            if(seats[row][students.get(i)]=='#') return false;
        }
        return true;
    }
    private boolean checkDiffRows(int mask1, int mask2){
        List<Integer> s1 = new ArrayList<>();
        List<Integer> s2 = new ArrayList<>();
        for(int i=0; i<n; i++){
            s1.add(mask1%2);
            s2.add(mask2%2);
            mask1/=2;
            mask2/=2;
        }
        for(int i=0; i<n; i++){
            if(s2.get(i)==0) continue;
            if(i-1>=0 && s1.get(i-1)==1) return false;
            if(i+1<n && s1.get(i+1)==1) return false;
        }
        return true;
    }
}