leetcode.5387. n个匹配方案数(状压dp)

$Description$
图片说明

$Code$
设 $dp[i][S]$ 表示前 $i$ 个帽子状态为 $S$ 的合法方案数， $S$ 表示 $[1,n]$ 里这些人是否戴了帽子的集合。
那么对于第 $i$ 个帽子,要么只有一个人戴，要么没有人戴。

所以对于合法的第 $j$ 个人戴这个帽子或者没有人戴。

$dp[i][\{0\}+S]+=dp[i-1][S]$ 没有人戴这个帽子。

$dp[i][\{j\}+S]+=dp[i-1][S]$ 合法的第 $j$ 个人戴这个帽子。

复杂度 $O(40*n*2^n)$

class Solution {
public:
    int g[43][11];
    int dp[42][1025]={0};
    const int mod=1e9+7;
    int numberWays(vector<vector<int>>& hat) {
        int n=hat.size();
        for(int i=0;i<n;i++){
            for(int j:hat[i])
            g[j][i]=1;
        }
        dp[0][0]=1;
        for(int i=1;i<=40;i++){
            for(int j=-1;j<n;j++){
                for(int k=0;k<(1<<n);k++){
                    if(j==-1)dp[i][0|k]=dp[i-1][k];
                    else{
                        if(g[i][j]&&!(1<<j&k)){
                            dp[i][1<<j|k]+=dp[i-1][k];
                            dp[i][1<<j|k]%=mod;
                        }
                    }
                }
            }
        }
        return dp[40][(1<<n)-1];
    }
};