原文链接: https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other

英文原文

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.

中文题目

总共有 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] 包含一个数字互不相同的整数列表。

通过代码

高赞题解

LeetCode还真是喜欢出状压的题目。还是老套路，看到某一个维度特别小（本题是$1\leq n\leq10$），就尝试在这一维进行状态压缩。

我们用一个$n$位的二进制数记录每个人是否戴上了帽子。因为是对人进行了状压，所以我们需要把题目给的每个人可以戴的帽子先转换成每个帽子可以匹配的人。之后，我们就可以遍历所有帽子，对于每一顶帽子，我们尝试把它分配给一个当前还没有帽子，并且能够匹配这顶帽子的人，来更新状态。

DP的转移方程为：

$$dp[state][i]=dp[state][i-1] + \sum dp[state - (1 << k)][i-1]$$

其中$state$表示当前的戴帽子情况，$i$表示分配第$i$号帽子，$k$满足$k\in S(i)$也即第$i$号帽子可以分配给第$k$个人，且$(state - (1 << k)) & (1 << k) = 0$，也即前一个状态中第$k$个人还没有戴帽子。

边界条件为：
$$dp[0][0]=1$$

也即所有人都还没戴上帽子，有1种方案。

因为转移方程只涉及$i$和$i-1$，所以可以用滚动数组做成一维空间。

总时间复杂度$O(nm2^n)$。

参考代码

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
  int numberWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<ll> dp(1 << n);
    dp[0] = 1;
    vector<set<int>> s(41);
    for (int i = 0; i < n; ++i)
      for (int hat : hats[i])
        s[hat].insert(i);
    for (int i = 1; i <= 40; ++i) {
      for (int state = (1 << n) - 1; state >= 0; --state) {
        for (int person : s[i]) {
          if (state & (1 << person))
            continue;
          int nxt = state + (1 << person);
          dp[nxt] += dp[state];
          dp[nxt] %= MOD;
        }
      }
    }
    return dp[(1 << n) - 1];
  }
};

统计信息

通过次数	提交次数	AC比率
2617	5596	46.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言