LC1434. 每个人戴不同帽子的方案数
总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。
- n == hats.length
- 1 <= n <= 10
- 1 <= hats[i].length <= 40
- 1 <= hats[i][j] <= 40
- hats[i] 包含一个数字互不相同的整数列表。
输入：hats = [[3,4],[4,5],[5]]
输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。
思路：动态规划
- 根据限制条件，帽子的数量较多，可以作为基数，给帽子分配人
- 利用动态规划记录中间状态
- f[i][j] 表示在有前 i 个帽子的前提下，分为 j（二进制表示谁有帽子）的方案数
- f[0][0] = 1，因为 i 和 i-1 的关系是继承，不是 +1，所以初始条件为 1。
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
|
class Solution {
public:
int mod = 1000000007;
int numberWays(vector<vector<int>>& hats) {
int n = hats.size();
int maxHatId = 0;
// 帽子的最大 id
for (int i = 0; i < n; ++i) {
for (int h : hats[i]) {
maxHatId = max(maxHatId , h);
}
}
// hatToPerson[h] 表示喜欢这顶帽子的人
vector<vector<int>> hatToPerson(maxHatId + 1);
for (int i = 0; i < n; ++i) {
for (int h : hats[i]) {
hatToPerson[h].emplace_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]) {
// 将此帽子给 j
if (mask & (1 << j)) {
f[i][mask] = (f[i-1][mask ^ (1 << j)] + f[i][mask]) % mod;
}
}
}
}
return f[maxHatId][(1 << n) - 1];
}
};
|