1. 问题背景与题目解析
LeetCode 1434题"每个人戴不同帽子的方案数"是一道典型的状态压缩动态规划问题。题目描述如下：有n个人和40种不同的帽子，帽子编号从1到40。给定一个列表hats，其中hats[i]表示第i个人可以戴的帽子列表。要求计算所有人戴帽子的方案数，使得没有两个人戴同一顶帽子。
这道题的核心在于处理"选择"与"限制"的关系。每个人只能从自己可选的帽子列表中选择一顶，同时全局需要满足帽子不重复的条件。这种"受限选择+全局唯一性"的组合特征，正是状态压缩DP的典型应用场景。
2. 状态压缩DP基础原理
状态压缩动态规划(State Compression DP)是一种处理组合优化问题的高效方法。当问题涉及多个元素的选择状态时，可以用二进制位来表示每个元素的选择情况。
对于本题，关键点在于：
- 帽子数量(40)远大于人数(n≤10)，因此应该对人进行状态压缩而非帽子
- 用二进制整数mask的每一位表示第i个人是否已经选到帽子
- dp[mask][j]表示前j顶帽子分配给mask表示的人们的方案数
状态转移方程为：
- 如果不选第j顶帽子：dp[mask][j] += dp[mask][j-1]
- 如果选第j顶帽子给第k个人：dp[mask][j] += dp[mask^(1<<k)][j-1] (当第k个人可以戴第j顶帽子时)
3. 详细解法实现
public int numberWays(List<List<Integer>> hats) { final int MOD = 1_000_000_007; int n = hats.size(); // 建立帽子到人的映射 List<Integer>[] hatToPeople = new List[41]; for (int i = 1; i <= 40; i++) hatToPeople[i] = new ArrayList<>(); for (int person = 0; person < n; person++) { for (int hat : hats.get(person)) { hatToPeople[hat].add(person); } } int[][] dp = new int[1 << n][41]; dp[0][0] = 1; for (int hat = 1; hat <= 40; hat++) { for (int mask = 0; mask < (1 << n); mask++) { // 不选当前帽子 dp[mask][hat] = dp[mask][hat - 1]; // 尝试选当前帽子给能戴的人 for (int person : hatToPeople[hat]) { if ((mask & (1 << person)) != 0) { dp[mask][hat] += dp[mask ^ (1 << person)][hat - 1]; dp[mask][hat] %= MOD; } } } } return dp[(1 << n) - 1][40]; }4. 关键优化与实现细节
映射预处理：将原始输入从"人到帽子"转换为"帽子到人"的映射，这样在状态转移时可以快速知道每顶帽子能分配给哪些人。
空间优化：注意到dp[hat]只依赖于dp[hat-1]，因此可以优化为两个一维数组，将空间复杂度从O(2^n * 40)降到O(2^n)。
位运算技巧：
mask & (1 << person)检查第person个人是否已分配帽子mask ^ (1 << person)将第person个人的状态取反
MOD处理：由于结果可能很大，题目要求对1e9+7取模。在每次加法操作后都要立即取模，避免溢出。
5. 复杂度分析
时间复杂度：O(40 * 2^n * n)
- 40顶帽子
- 2^n种状态
- 每顶帽子最多n个人可选
空间复杂度：O(2^n * 40) 或优化后的O(2^n)
对于n≤10的约束，2^10=1024，总操作次数约为40102410=409,600，完全在合理范围内。
6. 常见错误与调试技巧
初始化错误：忘记初始化dp[0][0]=1，导致所有结果都为0。
MOD处理遗漏：在状态转移的加法操作后忘记取模，导致结果错误或溢出。
位运算优先级：
mask & (1 << person) != 0需要括号，否则会先计算!=再&。索引越界：帽子编号是1-based，循环时注意从1到40而非0到39。
状态转移遗漏：忘记处理"不选当前帽子"的情况，只考虑了分配帽子的情况。
调试时可以打印中间状态：
if (hat <= 3) { // 只打印前几顶帽子调试 System.out.println("hat=" + hat + " mask=" + Integer.toBinaryString(mask) + " dp=" + dp[mask][hat]); }7. 相似题目推荐
- LeetCode 1125.最小的必要团队（状态压缩DP+集合覆盖）
- LeetCode 691.贴纸拼词（状态压缩DP+字符串处理）
- LeetCode 1349.参加考试的最大学生数（状态压缩DP+位运算）
- LeetCode 1986.完成任务的最少工作时间段（状态压缩DP+子集枚举）
- LeetCode 1494.并行课程II（状态压缩DP+课程安排）
这些题目都使用了状态压缩DP技术，但各自有不同的约束条件和状态设计方式，适合进一步练习和比较。
8. 实际应用场景
这种类型的问题在实际中有广泛的应用：
- 任务分配：将任务分配给工程师，每人有擅长的任务类型
- 课程安排：学生选课，课程有人数限制和时间冲突约束
- 资源调度：云计算中的虚拟机分配，满足资源需求且不冲突
- 团队组建：根据技能组合组建项目团队，覆盖所有所需技能
理解这类问题的解法有助于解决许多现实中的组合优化问题。状态压缩DP提供了一种系统化的方法，将看似复杂的约束条件转化为可计算的数学模型。