1434. 每个人戴不同帽子的方案数（状态压缩）

一般是把某一维数少的进行状态压缩

题目链接

const int mod=1e9+7;
int dp[45][1<<10];
/*
dp[i][bits] 前i顶帽子确定了归属，人戴帽子的状态为bits的方案数
dp[i][bits]->dp[i+1][n_bits]*/
class Solution {
public:int numberWays(vector<vector<int>>& hats) {int n=hats.size();int limit=1<<n;memset(dp,0,sizeof(dp));dp[0][0]=1;for(int h=1;h<=40;h++){for(int s=0;s<limit;s++){for(int i=0;i<n;i++){if((s>>i)&1) continue;if(find(hats[i].begin(),hats[i].end(),h)==hats[i].end()) continue;int tt=(1<<i)|s;dp[h][tt]=(dp[h][tt]+dp[h-1][s])%mod;}}for(int s=0;s<limit;s++){dp[h][s]=(dp[h][s]+dp[h-1][s])%mod;}}return dp[40][limit-1];}};