[状压dp]leeccode1434：每个人戴不同帽子的方案数(hard)

每个人戴不同帽子的方案数(hard)"/>

[状压dp]leeccode1434：每个人戴不同帽子的方案数(hard)

题目：

1434. 每个人戴不同帽子的方案数

题解：

• 思路：状压dp
• 解法：由于本人刚学习压状dp，且在《算法竞赛进阶指南》上学习了位运算相关的知识，做了两个状压dp的题，思路是学题解的，这里贴一下，记录下吧。
  
  

代码如下：

class Solution {
public://思路：状压dpint numberWays(vector<vector<int>>& hats) {int maxHatId=0,n=hats.size(),mod=1000000007;// 寻找最大序号帽子的id，便于返回dp[maxHatId][2^n-1]作答for(int i=0;i<n;++i){for(int h:hats[i]){maxHatId=max(maxHatId,h);}}// 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划vector<vector<int>> hatToPerson(maxHatId+1);for(int i=0;i<n;++i){for(int h:hats[i]){hatToPerson[h].push_back(i);}}// dp[i][state]表示我们处理了前i顶帽子，并且已经被分配帽子的人状态为state的方案数vector<vector<int>> dp(maxHatId+1,vector<int>(1<<n));// 边界条件，0个帽子分配给0个人，这也是一种方案数dp[0][0]=1;for(int i=1;i<=maxHatId;++i){for(int state=0;state<(1<<n);++state){// 如果第i顶帽子没有分配给任何人，那么前i-1顶帽子对应的分配状态就是state，而dii顶帽子对人的状态不会发生任何改变dp[i][state]=dp[i-1][state];for(int j:hatToPerson[i]){// 第i顶帽子戴在第j个人的头上，因此加上前i−1顶帽子对应的分配状态中，第j个人没有被分配帽子，而其它人的分配状态不变。if(state&(1<<j)){dp[i][state]+=dp[i-1][state^(1<<j)];dp[i][state]%=mod;}}}}//maxHatId顶帽子分配给n个人的方案数return dp[maxHatId][(1<<n)-1];}
};