1349. 参加考试的最大学生数 状态压缩

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-students-taking-exam
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，状态压缩枚举子集，长度8写就完事（其实WA了一次，因为dfs开始没写记忆化）

方法：状态压缩+记忆化搜索

1. 有座位设置为1，无状态设置为0，可以得到一个二进制组成数组
2. 考虑到可能存在大量的空状态，可用 dfs 方式来处理状压数据
3. 对于某个索引，如果前一个状态一致，则必然获取的后续元素最大值是一致的，可以进行缓存，索引长度8,上一个状态1e8，共有256种，因此存储 dp[8][256]
4. 枚举当前座位（二进制为 v）情况的子集，用 v&(i-1), 此时枚举的是非空子集（不要在循环内枚举包含空的子集，会死循环），后续枚举本行不选，占用座位为0的情况
5. 具体的，当前座位左右平移一位不能和原本分配的作为重合，也就是 (i&(i<<1))==0 && (i&(i>>1))==0，也可以只判断一侧，因为左边缘 11，左移过程中，最左是1，且后非0，不影响判断，右边缘右移过程中，右移是1，且的结果是1不影响判断。
6. 判断和上一排作为分配是否存在相邻，要求当前排左右平移一位不能合前一排相同，注意此时必须判断两侧，比如 10,1 右移一位 1,1 且的结果是1，但是左移结果是 100 和 1，不重合

class Solution {
    public int maxStudents(char[][] seats) {
        List<Integer> list = new ArrayList<>();
        for(char[] seat:seats){
            int v = 0;
            for(char c:seat){
                int curr = c=='.'?1:0;
                v = v*2+curr;
            }
            list.add(v);
        }

        for(int i = 0; i < 8; i++) Arrays.fill(dp[i],-1);

        return dfs(list,0,0);
    }
    
    int[][] dp = new int[8][256];

    private int dfs(List<Integer> list,int index,int preVal){
        if(index==list.size()) return 0;

        if(dp[index][preVal]!=-1) return dp[index][preVal];
        int ans = 0;
        int v = list.get(index);
        for(int i=v;i>0;i=v&(i-1)){
            if((i&(i<<1))==0 (preVal&(i<<1))==0 && (preVal&(i>>1))==0){
                ans = Math.max(dfs(list,index+1,i)+Integer.bitCount(i),ans);
            }
        }
        ans = Math.max(ans,dfs(list,index+1,0));
        dp[index][preVal] = ans;
        return ans;
    }
}