DeepSeek LeetCode 1434.每个个戴不同帽子的方案数 public int numberWays(List＜List＜Integer＞＞ hats)

这是一个典型的状态压缩DP问题，因为帽子数量最多40，人数最多10，我们不能以帽子作为状态，而应该以人作为状态。

解题思路

1. 状态定义
   dp[i][mask]表示考虑前 i 顶帽子，已经分配帽子的人集合为 mask 的方案数
   但这样空间太大：40 × 2^10 = 40 × 1024 = 40960，可行

2. 优化状态转移
   实际上我们可以反过来：让每个人选帽子
   对于每顶帽子，决定给哪个人（或者不给）

3. 更高效方法

   • 先预处理每顶帽子 → 哪些人喜欢这顶帽子
   • dp[mask]表示当前分配了 mask 这些人时的方案数
   • 遍历每顶帽子，尝试分配给 mask 中还没有帽子的人

4. 转移方程
   对于帽子 h，对于所有人 i (0…n-1)：
   如果 i 喜欢 h 且 mask 中第 i 位为 0：

   new_mask = mask | (1 << i) dp[new_mask] += dp[mask]

代码实现

classSolution{privatestaticfinalintMOD=1_000_000_007;publicintnumberWays(List<List<Integer>>hats){intn=hats.size();// 人数// 最大帽子编号是40，我们索引从1到40intmaxHat=40;// 预处理：每顶帽子 -> 喜欢它的人（二进制位表示）List<Integer>[]hatToPeople=newList[maxHat+1];for(inti=0;i<=maxHat;i++){hatToPeople[i]=newArrayList<>();}for(intperson=0;person<n;person++){for(inthat:hats.get(person)){hatToPeople[hat].add(person);}}// dp[mask] 表示当前已分配帽子的人集合为mask的方案数int[]dp=newint[1<<n];dp[0]=1;// 遍历每顶帽子for(inthat=1;hat<=maxHat;hat++){if(hatToPeople[hat].isEmpty())continue;// 复制当前状态，避免同顶帽子重复分配int[]next=dp.clone();// 对于这顶帽子，尝试分配给每个可能的人for(intperson:hatToPeople[hat]){for(intmask=0;mask<(1<<n);mask++){if((mask&(1<<person))==0){// 这个人还没戴帽子intnewMask=mask|(1<<person);next[newMask]=(next[newMask]+dp[mask])%MOD;}}}dp=next;}// 所有人都分配了帽子returndp[(1<<n)-1];}}

复杂度分析

• 时间复杂度：O(maxHat × 2^n × n)
  40 × 1024 × 10 ≈ 40万，实际上可以接受
• 空间复杂度：O(2^n)

关键点

1. 人少帽多→ 状态压缩人
2. 逐帽分配→ 避免重复分配同一帽子
3. 使用clone→ 确保同一顶帽子不会分配给多人

这个解法在 LeetCode 上可以通过，注意使用clone()或从大到小遍历 mask 来避免同帽子重复分配的问题。