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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

总共有 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 。

示例 4：

**输入：** hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
**输出：** 111

提示：

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

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

我们用 f[i][\textit{mask}] 表示我们处理了前 i 顶帽子，并且已经被分配帽子的人的状态为 mask 时的方案数。

对于帽子而言，我们从 1 开始编号，即 i 的范围为 [1, 40]。具体的原因在下文的状态转移方程中会有所体现，这是为了方便存储边界条件。

对于人而言，mask 是一个长度为 n 的二进制数，它的每一位对应了一个人的状态。如果 mask 的第 k 位为 0，那么第 k 个人还没有被分配帽子，如果为 1，那么第 k 个人被分配了帽子。

  • 例如当 mask} = (10010)_2 时，从右向左看，第 1 位和第 4 位为 1，表示第 1 和 4 个人被分配了帽子，而第 2，3，5 个人还没有被分配帽子。根据 mask 本身的性质，我们需要将人从 0 开始编号。

在状态的设计中，我们并没有存储每个人具体选择了哪顶帽子。这是因为在统计方案数时，我们只需要知道哪些帽子已经被选择过，以及哪些人已经选择过帽子就行了。

那么如何推导出状态转移方程呢？根据 f[i][\textit{mask}]，我们有两种转移的方法：

  • 如果第 i 顶帽子没有分配给任何人，那么会从 f[i-1][\textit{mask}] 转移而来，即表示前 i-1 顶帽子对应的分配状态就是 mask，而第 i 顶帽子不会对人的状态进行任何改变；

  • 如果第 i 顶帽子分配给了第 j 个人，那么我们首先需要确定：

    • 第 j 个人是喜欢第 i 顶帽子的；

    • mask 的第 j 位为 1，因为第 j 个人被分配了第 i 顶帽子。

    在满足了这两点要求之后，f[i][\textit{mask}] 就可以从 f[i-1][\textit{mask}’] 转移而来，其中 mask}’ 是将 mask 的第 j 位变成 0 得到的值。也就是说，前 i-1 顶帽子对应的分配状态中，第 j 个人没有被分配帽子，而其它人的分配状态不变。

因此我们就可以写出状态转移方程：

f[i][\textit{mask}] = f[i - 1][\textit{mask}] + \sum_{ {j \in \textit{mask} \wedge i \in \textit{hats}[j]} } f[i - 1][\textit{mask} \backslash j]

等式右侧的第一项不需要解释。第二项求和部分的条件 j \in \textit{mask 表示 mask 的第 j 位为 1，i \in \textit{hats}[j] 表示第 j 个人喜欢第 i 顶帽子，mask} \backslash j 表示将 mask 的第 j 位变成 0。这与上文的推导过程是一致的。

动态规划的边界条件为 f[0][0] = 1，这也是最初始的状态。最终的答案为 f[40][2^n-1]，其中 2^n-1 是包含 n 个 1 的二进制表示对应的十进制值。

小技巧

  • 我们可以用 mask & (1 << j) 或 (mask >> j) & 1 判断 mask 的第 j 位是否为 1；

  • 我们可以用 mask ^ (1 << j) 或 mask - (1 << j) 将 mask 的第 j 位从 1 变为 0。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using LL = long long;

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        // 找到帽子编号的最大值，这样我们只需要求出 f[maxhatid][2^n - 1] 作为答案
        int maxHatId = 0;
        for (int i = 0; i < n; ++i) {
            for (int h: hats[i]) {
                maxHatId = max(maxHatId, h);
            }
        }
        
        // 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划
        vector<vector<int>> hatToPerson(maxHatId + 1);
        for (int i = 0; i < n; ++i) {
            for (int h: hats[i]) {
                hatToPerson[h].push_back(i);
            }
        }
        
        vector<vector<int>> f(maxHatId + 1, vector<int>(1 << n));
        // 边界条件
        f[0][0] = 1;
        for (int i = 1; i <= maxHatId; ++i) {
            for (int mask = 0; mask < (1 << n); ++mask) {
                f[i][mask] = f[i - 1][mask];
                for (int j: hatToPerson[i]) {
                    if (mask & (1 << j)) {
                        f[i][mask] += f[i - 1][mask ^ (1 << j)];
                        f[i][mask] %= mod;
                    }
                }
            }
        }
        
        return f[maxHatId][(1 << n) - 1];
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        mod = 10**9 + 7
        n = len(hats)
        # 找到帽子编号的最大值，这样我们只需要求出 f[maxhatid][2^n - 1] 作为答案
        maxHatId = max(max(ids) for ids in hats)
        
        # 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划
        hatToPerson = collections.defaultdict(list)
        for i in range(n):
            for h in hats[i]:
                hatToPerson[h].append(i)
        
        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]
        # 边界条件
        f[0][0] = 1
        for i in range(1, maxHatId + 1):
            for mask in range(1 << n):
                f[i][mask] = f[i - 1][mask]
                for j in hatToPerson[i]:
                    if mask & (1 << j):
                        f[i][mask] += f[i - 1][mask ^ (1 << j)]
                f[i][mask] %= mod
        
        return f[maxHatId][(1 << n) - 1]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int numberWays(List<List<Integer>> hats) {
        final int MOD = 1000000007;
        int n = hats.size();
        // 找到帽子编号的最大值，这样我们只需要求出 f[maxhatid][2^n - 1] 作为答案
        int maxHatId = 0;
        for (int i = 0; i < n; ++i) {
            List<Integer> list = hats.get(i);
            for (int h: list) {
                maxHatId = Math.max(maxHatId, h);
            }
        }
        
        // 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划
        List<List<Integer>> hatToPerson = new ArrayList<List<Integer>>();
        for (int i = 0; i <= maxHatId; i++) {
            hatToPerson.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < n; ++i) {
            List<Integer> list = hats.get(i);
            for (int h: list) {
                hatToPerson.get(h).add(i);
            }
        }
        
        int[][] f = new int[maxHatId + 1][1 << n];
        // 边界条件
        f[0][0] = 1;
        for (int i = 1; i <= maxHatId; ++i) {
            for (int mask = 0; mask < (1 << n); ++mask) {
                f[i][mask] = f[i - 1][mask];
                List<Integer> list = hatToPerson.get(i);
                for (int j: list) {
                    if ((mask & (1 << j)) != 0) {
                        f[i][mask] += f[i - 1][mask ^ (1 << j)];
                        f[i][mask] %= MOD;
                    }
                }
            }
        }
        
        return f[maxHatId][(1 << n) - 1];
    }
}

复杂度分析

  • 时间复杂度：O(2^n * h)，其中 h 表示 hats 中的元素个数。

    • 我们需要 O(h) 的时间得到帽子编号的最大值；

    • 我们需要 O(h) 的时间构造数组 hatToPerson；

    • 在动态规划过程中，枚举 mask 对应的循环的时间复杂度为 O(2^n)，而枚举 i 和 j 对应循环的时间复杂度总计为 O(h)，因此动态规划的时间复杂度为 O(2^n * h)。

  • 空间复杂度：O(2^n * m + h) 或 O(2^n + h)，其中 m 表示帽子编号的最大值。

    • 我们需要 O(h) 的空间存储数组 hatToPerson；

    • 我们需要 O(2^n * m) 的空间存储动态规划的结果。注意到在 f[i][\textit{mask}] 只会从 f[i - 1][..] 转移而来，因此我们也可以使用两个 O(2^n) 的一维数组，交替地进行状态转移，空间复杂度降低至 O(2^n)。

 Comments
On this page
1434-每个人戴不同帽子的方案数