Hard

题目描述

有 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) 的排列数为 24。

提示：

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] 包含一个不重复的整数列表

解题思路

这是一道经典的动态规划 + 状态压缩问题。

解题思路：

传统思路是枚举每个人选择哪顶帽子，但这样状态转移比较复杂。我们可以换个角度思考：枚举每顶帽子分配给哪个人。

状态设计：

  • dp[hat][mask] 表示考虑前 hat 顶帽子，已经戴帽子的人的状态为 mask 时的方案数
  • mask 是一个二进制数，第 i 位为 1 表示第 i 个人已经戴了帽子

状态转移： 对于第 hat 顶帽子，我们有两种选择：

  1. 不给任何人戴：dp[hat][mask] = dp[hat-1][mask]
  2. 给某个喜欢这顶帽子且还没戴帽子的人戴：dp[hat][mask] += dp[hat-1][mask^(1<<person)]

优化： 由于帽子数量最多 40，人数最多 10，我们可以先预处理出每顶帽子被哪些人喜欢，然后只枚举存在的帽子。

边界条件： dp[0][0] = 1，表示没有考虑任何帽子且没有人戴帽子时有 1 种方案。

答案： dp[maxHat][allPeopleMask]，其中 allPeopleMask = (1<<n) - 1。

代码实现

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        const int MOD = 1e9 + 7;
        int n = hats.size();
        
        // 预处理：每顶帽子被哪些人喜欢
        vector<vector<int>> hatToPeople(41);
        for (int i = 0; i < n; i++) {
            for (int hat : hats[i]) {
                hatToPeople[hat].push_back(i);
            }
        }
        
        // dp[mask] 表示当前状态下的方案数
        vector<int> dp(1 << n, 0);
        dp[0] = 1;
        
        // 枚举每顶帽子
        for (int hat = 1; hat <= 40; hat++) {
            if (hatToPeople[hat].empty()) continue;
            
            // 从大到小枚举状态，避免重复计算
            for (int mask = (1 << n) - 1; mask >= 0; mask--) {
                if (dp[mask] == 0) continue;
                
                // 尝试把当前帽子给每个喜欢它且还没戴帽子的人
                for (int person : hatToPeople[hat]) {
                    if (!(mask & (1 << person))) {
                        dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(hats)
        
        # 预处理：每顶帽子被哪些人喜欢
        hat_to_people = [[] for _ in range(41)]
        for i in range(n):
            for hat in hats[i]:
                hat_to_people[hat].append(i)
        
        # dp[mask] 表示当前状态下的方案数
        dp = [0] * (1 << n)
        dp[0] = 1
        
        # 枚举每顶帽子
        for hat in range(1, 41):
            if not hat_to_people[hat]:
                continue
            
            # 从大到小枚举状态，避免重复计算
            for mask in range((1 << n) - 1, -1, -1):
                if dp[mask] == 0:
                    continue
                
                # 尝试把当前帽子给每个喜欢它且还没戴帽子的人
                for person in hat_to_people[hat]:
                    if not (mask & (1 << person)):
                        dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD
        
        return dp[(1 << n) - 1]

public class Solution {
    public int NumberWays(IList<IList<int>> hats) {
        const int MOD = 1000000007;
        int n = hats.Count;
        
        // 预处理：每顶帽子被哪些人喜欢
        List<int>[] hatToPeople = new List<int>[41];
        for (int i = 0; i <= 40; i++) {
            hatToPeople[i] = new List<int>();
        }
        
        for (int i = 0; i < n; i++) {
            foreach (int hat in hats[i]) {
                hatToPeople[hat].Add(i);
            }
        }
        
        // dp[mask] 表示当前状态下的方案数
        int[] dp = new int[1 << n];
        dp[0] = 1;
        
        // 枚举每顶帽子
        for (int hat = 1; hat <= 40; hat++) {
            if (hatToPeople[hat].Count == 0) continue;
            
            // 从大到小枚举状态，避免重复计算
            for (int mask = (1 << n) - 1; mask >= 0; mask--) {
                if (dp[mask] == 0) continue;
                
                // 尝试把当前帽子给每个喜欢它且还没戴帽子的人
                foreach (int person in hatToPeople[hat]) {
                    if ((mask & (1 << person)) == 0) {
                        dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var numberWays = function(hats) {
    const MOD = 1000000007;
    const n = hats.length;
    
    // Create hat-to-people mapping
    const hatToPeople = {};
    for (let i = 0; i < n; i++) {
        for (let hat of hats[i]) {
            if (!hatToPeople[hat]) hatToPeople[hat] = [];
            hatToPeople[hat].push(i);
        }
    }
    
    const hatList = Object.keys(hatToPeople).map(Number).sort((a, b) => a - b);
    const memo = new Map();
    
    function dp(hatIdx, mask) {
        if (mask === (1 << n) - 1) return 1;
        if (hatIdx >= hatList.length) return 0;
        
        const key = `${hatIdx},${mask}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = dp(hatIdx + 1, mask);
        
        const hat = hatList[hatIdx];
        for (let person of hatToPeople[hat]) {
            if (!(mask & (1 << person))) {
                result = (result + dp(hatIdx + 1, mask | (1 << person))) % MOD;
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值
时间复杂度O(40 × 2^n × n)
空间复杂度O(2^n + 40×n)

其中 n 是人数，最多为 10。时间复杂度中的 40 是帽子数量，2^n 是状态数，n 是每个状态下最多检查的人数。空间复杂度主要是 dp 数组的 O(2^n) 和预处理数组的 O(40×n)。

相关题目