企业官网建设流程全解析

1. 问题背景与题目解析

LeetCode 1434题"每个人戴不同帽子的方案数"是一道典型的动态规划与状态压缩结合的题目。题目描述如下：有n个人和40种不同的帽子，帽子编号从1到40。给定一个列表hats，其中hats[i]是第i个人可以戴的所有帽子的列表。要求计算每个人戴一顶帽子且所有帽子互不相同的方案数。

这道题的核心在于：

• 每个人只能选择自己列表中的帽子
• 所有被选中的帽子必须互不相同
• 需要计算所有可能的分配方案数

2. 解题思路分析

2.1 暴力搜索的不可行性

最直观的想法是使用回溯法枚举所有可能的分配方案。对于n个人和m顶帽子，时间复杂度为O(m^n)。当n=10，m=40时，这显然不可行。

2.2 动态规划的状态设计

我们需要设计一个状态表示当前的分配情况。考虑到：

1. 帽子数量最多40种，可以用一个40位的二进制数表示哪些帽子已被使用
2. 需要记录当前已经分配到了第几个人

因此，状态可以设计为dp[i][mask]，表示前i个人已经分配完帽子，且当前已使用的帽子集合为mask时的方案数。

2.3 状态转移方程

对于第i个人，遍历他所有可选的帽子：

• 如果某顶帽子还未被使用(mask对应位为0)
• 则可以将其分配给第i个人，并更新mask
• 方案数累加上dp[i-1][old_mask]

状态转移方程为： dp[i][mask] += dp[i-1][mask ^ (1 << hat)] for hat in hats[i-1] if (mask & (1 << hat))

3. 具体实现与优化

3.1 初始状态

dp[0][0] = 1 # 0个人分配0顶帽子的方案数为1 其他dp[0][...] = 0

3.2 Java实现代码

public int numberWays(List<List<Integer>> hats) { int n = hats.size(); int mod = 1_000_000_007; // 预处理：将帽子编号映射到0-39 Map<Integer, Integer> hatToIdx = new HashMap<>(); int idx = 0; for (List<Integer> list : hats) { for (int hat : list) { if (!hatToIdx.containsKey(hat)) { hatToIdx.put(hat, idx++); } } } int totalHats = hatToIdx.size(); int[][] dp = new int[n+1][1 << totalHats]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int mask = 0; mask < (1 << totalHats); mask++) { dp[i][mask] = dp[i-1][mask]; // 不选任何帽子 for (int hat : hats.get(i-1)) { int hatIdx = hatToIdx.get(hat); if ((mask & (1 << hatIdx)) != 0) { dp[i][mask] += dp[i-1][mask ^ (1 << hatIdx)]; dp[i][mask] %= mod; } } } } return dp[n][(1 << totalHats) - 1]; }

3.3 优化空间复杂度

注意到dp[i]只依赖于dp[i-1]，可以将空间优化到O(2^m)：

public int numberWays(List<List<Integer>> hats) { int n = hats.size(); int mod = 1_000_000_007; Map<Integer, Integer> hatToIdx = new HashMap<>(); int idx = 0; for (List<Integer> list : hats) { for (int hat : list) { if (!hatToIdx.containsKey(hat)) { hatToIdx.put(hat, idx++); } } } int totalHats = hatToIdx.size(); int[] dp = new int[1 << totalHats]; dp[0] = 1; for (int i = 0; i < n; i++) { int[] newDp = Arrays.copyOf(dp, dp.length); for (int mask = 0; mask < (1 << totalHats); mask++) { for (int hat : hats.get(i)) { int hatIdx = hatToIdx.get(hat); if ((mask & (1 << hatIdx)) != 0) { newDp[mask] += dp[mask ^ (1 << hatIdx)]; newDp[mask] %= mod; } } } dp = newDp; } return dp[(1 << totalHats) - 1]; }

4. 复杂度分析

时间复杂度：O(n * 2^m * k)，其中n是人数，m是帽子种类数，k是每个人平均可选的帽子数。由于m最多为40，2^40显然太大，但题目中帽子编号是离散的，实际m是不同帽子编号的数量。

空间复杂度：优化后为O(2^m)，同样取决于实际不同的帽子数量。

5. 实际编码中的注意事项

1. 帽子编号映射：原始帽子编号可能很大且不连续，需要先映射到连续的索引(0到m-1)，否则状态压缩会浪费大量空间。

2. 模运算：题目要求结果对1e9+7取模，需要在每次状态转移时都进行模运算，防止溢出。

3. 初始化：dp[0][0] = 1的初始条件容易被忽略，它表示0个人分配0顶帽子的方案数为1。

4. 边界情况：当人数多于帽子数时，直接返回0；当帽子列表为空时也需要特殊处理。

5. 状态转移方向：在空间优化版本中，要注意不能原地修改dp数组，需要先复制一份。

6. 类似题目扩展

1. LeetCode 698. 划分为k个相等的子集：类似的状态压缩DP思想
2. LeetCode 526. 优美的排列：排列问题与状态压缩
3. LeetCode 1349. 参加考试的最大学生数：棋盘类状态压缩DP

这类问题的共同特点是：

• 需要记录某种"使用情况"
• 状态空间较大但可以压缩表示
• 转移需要考虑所有可能的合法选择

7. 个人解题心得

在实际解决这道题时，我最初尝试了回溯法，很快发现对于较大n会超时。然后意识到需要记录帽子的使用情况，自然想到状态压缩。几个关键点：

1. 帽子编号需要重新映射，否则状态压缩的空间会爆炸
2. 状态转移时，当前人可以选择不戴任何帽子（如果允许的话），但题目似乎要求每人必须戴一顶
3. 空间优化版本中，内层循环的顺序很重要，需要确保不会重复计算

对于状态压缩DP问题，我的经验是：

• 先明确哪些信息需要被记录在状态中
• 设计合理的状态表示方式（通常是位掩码）
• 仔细推导状态转移方程，考虑所有可能的转移来源
• 注意空间优化时不能破坏依赖关系

这道题很好地展示了如何将看似复杂的组合问题转化为动态规划问题，通过状态压缩技术高效求解。掌握这类问题的解法，对于解决LeetCode中许多hard级别的题目都很有帮助。