1. 问题背景与题目解析
LeetCode 1434题"每个人戴不同帽子的方案数"是一道典型的状态压缩动态规划问题。题目给定一个列表hats，其中hats[i]表示第i个人可以选择的帽子列表。要求计算所有人戴帽子的总方案数，且满足以下条件：
- 每个人都必须戴一顶帽子
- 不同的人不能戴同一顶帽子
输入格式为List<List >，输出为一个整数表示方案数，由于结果可能很大，需要对10^9+7取模。
2. 状态压缩DP的核心思想
2.1 为什么需要状态压缩
这道题的关键在于帽子数量可能很大（最多40顶），而人数较少（最多10人）。直接暴力枚举所有可能的分配方案显然不可行，时间复杂度会爆炸。
状态压缩DP通过将"帽子使用情况"这个状态用一个二进制数表示，每一位代表一顶帽子是否被使用过。对于10个人和40顶帽子的情况，状态空间是2^40，仍然太大。因此需要更聪明的状态表示。
2.2 逆向思维：从帽子角度考虑
更优的解法是转换视角，不从人分配帽子，而是考虑每顶帽子可以分配给哪些人。这样状态可以表示为"已经分配了哪些人"，由于人数最多10人，状态空间只有2^10=1024种可能，大大降低了复杂度。
3. 详细解法与代码实现
3.1 预处理帽子到人的映射
首先需要将输入数据转换格式，建立每顶帽子对应哪些人可以戴它的映射：
Map<Integer, List<Integer>> hatToPeople = new HashMap<>(); for (int person = 0; person < hats.size(); person++) { for (int hat : hats.get(person)) { hatToPeople.putIfAbsent(hat, new ArrayList<>()); hatToPeople.get(hat).add(person); } }3.2 DP状态定义与转移
定义dp[mask]表示当前已经分配的人员集合为mask时的方案数。初始状态dp[0]=1，表示没有任何人分配帽子时有1种方案。
对于每顶帽子，我们遍历所有可能的人员分配：
int[] dp = new int[1 << n]; dp[0] = 1; for (int hat : hatToPeople.keySet()) { int[] newDp = dp.clone(); for (int person : hatToPeople.get(hat)) { for (int mask = 0; mask < (1 << n); mask++) { if ((mask & (1 << person)) == 0) { newDp[mask | (1 << person)] += dp[mask]; newDp[mask | (1 << person)] %= MOD; } } } dp = newDp; }3.3 最终结果与边界处理
最终结果是dp[(1<<n)-1]，即所有人都分配了帽子的方案数。需要注意处理一些边界情况：
- 如果帽子总数小于人数，直接返回0
- 结果需要对10^9+7取模
- 需要处理重复帽子编号的情况
4. 复杂度分析与优化
4.1 时间复杂度
设n为人数量，h为帽子数量：
- 预处理：O(n*h)
- DP过程：O(h * n * 2^n) 总复杂度为O(h * n * 2^n)，当n=10时，2^10=1024，是可接受的。
4.2 空间优化
可以使用滚动数组优化空间，因为每顶帽子只依赖于前一个状态：
int[] dp = new int[1 << n]; dp[0] = 1; for (int hat : hatToPeople.keySet()) { int[] newDp = Arrays.copyOf(dp, dp.length); for (int person : hatToPeople.get(hat)) { for (int mask = (1 << n) - 1; mask >= 0; mask--) { if ((mask & (1 << person)) == 0) { newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD; } } } dp = newDp; }5. 完整代码实现
class Solution { private static final int MOD = 1000000007; public int numberWays(List<List<Integer>> hats) { int n = hats.size(); Map<Integer, List<Integer>> hatToPeople = new HashMap<>(); for (int person = 0; person < n; person++) { for (int hat : hats.get(person)) { hatToPeople.putIfAbsent(hat, new ArrayList<>()); hatToPeople.get(hat).add(person); } } int[] dp = new int[1 << n]; dp[0] = 1; for (int hat : hatToPeople.keySet()) { int[] newDp = Arrays.copyOf(dp, dp.length); for (int person : hatToPeople.get(hat)) { for (int mask = 0; mask < (1 << n); mask++) { if ((mask & (1 << person)) == 0) { newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD; } } } dp = newDp; } return dp[(1 << n) - 1]; } }6. 常见错误与调试技巧
6.1 初始化错误
常见错误是忘记初始化dp[0]=1，这会导致所有结果都为0。记住空集合也是一种有效状态。
6.2 状态转移顺序
在更新dp数组时，如果正向遍历mask，会导致同一顶帽子被多次分配。应该使用newDp数组或反向遍历mask。
6.3 取模运算
忘记在每次加法后取模可能导致整数溢出。Java中虽然不会报错，但结果会不正确。
6.4 帽子编号处理
题目没有说明帽子编号的范围，实际测试用例中可能有重复编号或非常大的编号。使用Map而不是数组来存储帽子到人的映射更安全。
7. 类似题目推荐
- LeetCode 698. 划分为k个相等的子集（Partition to K Equal Sum Subsets）
- LeetCode 526. 优美的排列（Beautiful Arrangement）
- LeetCode 691. 贴纸拼词（Stickers to Spell Word）
- LeetCode 1125. 最小的必要团队（Smallest Sufficient Team）
这些题目都使用了状态压缩DP的技巧，可以帮助加深对这种解题思路的理解。
8. 实际应用场景
这种类型的问题在实际中有很多应用，比如：
- 任务分配问题：将任务分配给工人，每个工人有自己擅长的任务类型
- 课程安排：学生选课，每门课有容量限制
- 资源调度：将有限的资源分配给多个项目
理解这类问题的解法有助于解决实际中的资源分配和组合优化问题。
9. 个人解题心得
在解决这类状态压缩DP问题时，我总结了几个关键点：
状态表示要尽可能小：这道题巧妙之处在于从帽子角度考虑，将状态表示为人员集合而非帽子集合，大大降低了状态空间。
预处理很重要：将输入数据转换为更方便处理的形式（如帽子到人的映射）可以简化后续逻辑。
遍历顺序很关键：DP的状态转移顺序会影响正确性，需要仔细考虑。
边界条件检查：特别是当帽子数量小于人数时，直接返回0可以避免不必要的计算。
这道题很好地展示了如何通过改变视角来优化算法，是学习状态压缩DP的经典例题。