每个人戴不同帽子的方案数(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];}
};
更多推荐
[状压dp]leeccode1434:每个人戴不同帽子的方案数(hard)
发布评论