What is the primary pattern in Number of Ways to Wear Different Hats to Each Other?

The primary pattern is state transition dynamic programming using bitmasking to represent people assigned hats.

How do I efficiently implement bitmask DP for this hats problem?

Represent assigned people as bits in an integer. Iterate over hats, updating DP states by setting bits for each possible person assignment without conflicts.

Can this approach handle all n <= 10 people?

Yes, with bitmask DP the 2^n states are feasible for n up to 10, ensuring quick updates for each hat.

Why not use permutations to solve this problem?

Direct permutations are inefficient because checking constraints for every arrangement grows factorially, while DP with bitmask tracks valid assignments efficiently.

How do I prevent double counting in overlapping hat preferences?

Update DP states in a way that each new hat only augments states for people not yet assigned, ensuring each assignment is counted exactly once.

#1434

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

每个人戴不同帽子的方案数

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。由于答案可能很大，请返回它对 10^9 + 7 取余…

数组动态规划位运算位掩码

题目描述

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。

给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。

示例 1：

输入：hats = [[3,4],[4,5],[5]]
输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。

示例 2：

输入：hats = [[3,5,1],[3,5]]
输出：4
解释：总共有 4 种安排帽子的方法：
(3,5)，(5,3)，(1,3) 和 (1,5)

示例 3：

输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
输出：24
解释：每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24 。

提示：

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] 包含一个数字互不相同的整数列表。

lightbulb

解题思路

方法一：状态压缩动态规划

我们注意到 $n$ 不超过 $10$ ，因此我们考虑使用状态压缩动态规划的方法求解。

我们定义 $f[i][j]$ 表示在前 $i$ 个帽子中，当前被分配的人的状态为 $j$ 时的方案数。其中 $j$ 是一个二进制数，表示当前被分配的人的集合。初始时 $f[0][0]=1$ ，答案为 $f[m][2^n - 1]$ ，其中 $m$ 是帽子的最大编号，而 $n$ 是人的数量。

考虑 $f[i][j]$ ，如果第 $i$ 个帽子不分配给任何人，那么 $f[i][j]=f[i-1][j]$ ；如果第 $i$ 个帽子分配给了喜欢它的人 $k$ ，那么 $f[i][j]=f[i-1][j \oplus 2^k]$ 。这里 $\oplus$ 表示异或运算。因此我们可以得到状态转移方程：

f[i][j]=f[i-1][j]+ \sum_{k \in like[i]} f[i-1][j \oplus 2^k]

其中 $like[i]$ 表示喜欢第 $i$ 个帽子的人的集合。

最终的答案即为 $f[m][2^n - 1]$ ，注意答案可能很大，需要对 $10^9 + 7$ 取模。

时间复杂度 $O(m \times 2^n \times n)$ ，空间复杂度 $O(m \times 2^n)$ 。其中 $m$ 是帽子的最大编号，本题中 $m \leq 40$ ；而 $n$ 是人的数量，本题中 $n \leq 10$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        g = defaultdict(list)
        for i, h in enumerate(hats):
            for v in h:
                g[v].append(i)
        mod = 10**9 + 7
        n = len(hats)
        m = max(max(h) for h in hats)
        f = [[0] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 1
        for i in range(1, m + 1):
            for j in range(1 << n):
                f[i][j] = f[i - 1][j]
                for k in g[i]:
                    if j >> k & 1:
                        f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod
        return f[m][-1]

speed

复杂度分析

指标	值
时间	complexity is O(k * n * 2^n) where k is the number of hats and n is the number of people, as each hat can update all DP states. Space complexity is O(k * 2^n) to store DP states for each hat.
空间	O(k \cdot 2^n)

psychology

面试官常问的追问

外企场景

question_mark
Focus on bitmask representation of people assignments.
question_mark
Expect efficient state transition DP instead of brute-force permutation generation.
question_mark
Watch for edge cases where a person prefers no hats or multiple hats overlap.

warning

常见陷阱

外企场景

error
Incorrectly updating DP states leading to double counting.
error
Failing to handle hats that no one prefers, causing state inconsistencies.
error
Ignoring modulus constraints which can cause integer overflow in large counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Restrict hats to a smaller fixed set and test DP scalability.
arrow_right_alt
Allow multiple people to share the same hat and analyze state changes.
arrow_right_alt
Compute the minimum number of hats needed for a valid assignment instead of counting all ways.

help

常见问题

外企场景

继续练习

#1349 参加考试的最大学生数 #1595 连通两组点的最小成本 #1255 得分最高的单词集合