There are n
people and 40 types of hats labeled from 1 to 40.
Given a list of list of integers hats
, where hats[i]
is a list of all hats preferred by the i-th
person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 10^9 + 7
.
Example 1:
Input: hats = [[3,4],[4,5],[5]] Output: 1 Explanation: There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.
Example 2:
Input: hats = [[3,5,1],[3,5]] Output: 4 Explanation: There are 4 ways to choose hats (3,5), (5,3), (1,3) and (1,5)
Example 3:
Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] Output: 24 Explanation: Each person can choose hats labeled from 1 to 4. Number of Permutations of (1,2,3,4) = 24.
Example 4:
Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]] Output: 111
Constraints:
n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i]
contains a list of unique integers.
Solution: DP
dp[i][j] := # of ways using first i hats, j is the bit mask of people wearing hats.
e.g. dp[3][101] == # of ways using first 3 hats that people 1 and 3 are wearing hats.
init dp[0][0] = 1
dp[i][mask | (1 << p)] = dp[i-1][mask | (1 << p)] + dp[i-1][mask], where people p prefers hats i.
ans: dp[nHat][1…1]
Time complexity: O(2^n * h * n)
Space complexity: O(2^n * h) -> O(2^n)
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 |
// Author: Huahua class Solution { public: int numberWays(vector<vector<int>>& hats) { constexpr int kHat = 40; constexpr int kMod = 1e9 + 7; const int n = hats.size(); vector<vector<int>> people(kHat + 1); // hat -> {people} for (int i = 0; i < n; ++i) for (int hat : hats[i]) people[hat].push_back(i); // dp[i][j] := # of ways using first i hats where j is bit mask of people wearing hats. vector<vector<int>> dp(kHat + 1, vector<int>(1 << n)); dp[0][0] = 1; for (int i = 1; i <= kHat; ++i) { dp[i] = dp[i - 1]; for (int mask = (1 << n) - 1; mask >= 0; --mask) for (int p : people[i]) { if (mask & (1 << p)) continue; dp[i][mask | (1 << p)] += dp[i - 1][mask]; dp[i][mask | (1 << p)] %= kMod; } } return dp.back().back(); } }; |
O(2^n) memory
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 |
// Author: Huahua class Solution { public: int numberWays(vector<vector<int>>& hats) { constexpr int kHat = 40; constexpr int kMod = 1e9 + 7; const int n = hats.size(); vector<vector<int>> people(kHat + 1); // hat -> {people} for (int i = 0; i < n; ++i) for (int hat : hats[i]) people[hat].push_back(i); // dp([i])[j] := # of ways using first i hats where j is bit mask of people wearing hat. vector<int> dp(1 << n); dp[0] = 1; for (int i = 1; i <= kHat; ++i) for (int mask = (1 << n) - 1; mask >= 0; --mask) for (int p : people[i]) { if (mask & (1 << p)) continue; dp[mask | (1 << p)] += dp[mask]; dp[mask | (1 << p)] %= kMod; } return dp.back(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment