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

这是一个典型的状态压缩DP问题因为帽子数量最多40人数最多10我们不能以帽子作为状态而应该以人作为状态。解题思路状态定义dp[i][mask]表示考虑前 i 顶帽子已经分配帽子的人集合为 mask 的方案数但这样空间太大40 × 2^10 40 × 1024 40960可行优化状态转移实际上我们可以反过来让每个人选帽子对于每顶帽子决定给哪个人或者不给更高效方法先预处理每顶帽子 → 哪些人喜欢这顶帽子dp[mask]表示当前分配了 mask 这些人时的方案数遍历每顶帽子尝试分配给 mask 中还没有帽子的人转移方程对于帽子 h对于所有人 i (0…n-1)如果 i 喜欢 h 且 mask 中第 i 位为 0new_mask mask | (1 i) dp[new_mask] dp[mask]代码实现classSolution{privatestaticfinalintMOD1_000_000_007;publicintnumberWays(ListListIntegerhats){intnhats.size();// 人数// 最大帽子编号是40我们索引从1到40intmaxHat40;// 预处理每顶帽子 - 喜欢它的人二进制位表示ListInteger[]hatToPeoplenewList[maxHat1];for(inti0;imaxHat;i){hatToPeople[i]newArrayList();}for(intperson0;personn;person){for(inthat:hats.get(person)){hatToPeople[hat].add(person);}}// dp[mask] 表示当前已分配帽子的人集合为mask的方案数int[]dpnewint[1n];dp[0]1;// 遍历每顶帽子for(inthat1;hatmaxHat;hat){if(hatToPeople[hat].isEmpty())continue;// 复制当前状态避免同顶帽子重复分配int[]nextdp.clone();// 对于这顶帽子尝试分配给每个可能的人for(intperson:hatToPeople[hat]){for(intmask0;mask(1n);mask){if((mask(1person))0){// 这个人还没戴帽子intnewMaskmask|(1person);next[newMask](next[newMask]dp[mask])%MOD;}}}dpnext;}// 所有人都分配了帽子returndp[(1n)-1];}}复杂度分析时间复杂度O(maxHat × 2^n × n)40 × 1024 × 10 ≈ 40万实际上可以接受空间复杂度O(2^n)关键点人少帽多→ 状态压缩人逐帽分配→ 避免重复分配同一帽子使用clone→ 确保同一顶帽子不会分配给多人这个解法在 LeetCode 上可以通过注意使用clone()或从大到小遍历 mask 来避免同帽子重复分配的问题。