题目大意：
每个人戴不同帽子的方案数
总共有 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] 包含一个数字互不相同的整数列表。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1434
解题思路分析：
这是一道不错的题目，运用到的知识点很全面，也是面试官比较青睐的一类题型。
回到题目，我们看到本题的结果会非常大，通常情况下，这需要使用到动态规划（DP）来解题。本题也不例外，另外，之前的文章我也多次强调过，所有的动态规划实际上都可以转化为递归加记忆数组的形式来解题。个人认为相比于DP，这种解题方式更像是dfs，也更便于理解。本题我们也会使用递归方式来做讲解。
本题的大意是（最多）10个人去选择40顶帽子，并且每个人的选择不能重复。题目给出的参数是每个人可以选择的帽子列表，因此在递归时，我们可以按照人的编号进行递归，对于当前人，它可以选择的帽子是题目给定的列表，我们在当前递归中尝试循环选择每一顶帽子，如果当前帽子还没有被他人指定，那么我们可以选择当前帽子，并递归到下一个人。循环中的每一个递归函数都会返回一个结果（选择的可能性），我们将所有结果相加，即是本层递归的返回结果。这个递归过程实际上相当于dfs找路径数，当递归完最后一个人后，结束当前路径递归并返回1。
以上是典型的递归思路，并没有太大的难度，但是本题的难点在于如何构建记忆数组。如果你熟悉我们文章的话，你应该了解，记忆数组的定义实际上取决于递归函数中的参数。那些可变的参数即是记忆数组（DP数组）的组成。例如本题，记忆数组中的可变参数是记录当前人的index，以及哪些帽子已经被选择过的状态信息。两个变量参数代表需要2维记忆数组。index还好说，被选择过的状态信息也不难，我们可以使用一个boolean型的访问数组来表示，并且该boolean数组也可以使用二进制数来替代，但问题是题目给出一共有40顶帽子，也就是说我们需要一个40位的二进制数来记录每顶帽子的选择情况，这显然超出了int型的最大值。因此这会导致建立二维记忆数组时报错。
这就是本题另一个精妙之处，如果你不能想通这个难点，你就无法进阶到动态规划的下一个境界。实际上对于这类问题，我们需要换个角度去思考，当发现给定的参数的数量级超越了记忆数组的承受范围时，我们应尝试变换题目的参数，比如本题给出的数组hats ，它代表了每个人所有喜欢帽子的列表。假设人和帽子之间的关系是相互的，我们可以将该变量转化为每顶帽子喜欢人的列表。这样一来，在递归时，我们以帽子的index作为递归对象，递归中，循环该帽子所有喜欢的人的列表，如果当前人已经被其他帽子选择时，跳过。否则选择当前人，并递归到下一顶帽子。当所有人都被帽子选择时，返回1。当递归完最后一顶帽子后仍有人尚未被帽子选择时，返回0。这样，我们在建立记忆数组时，一维变量是帽子的index，二维变量是所有人被选择的状态，因为题目中最多只有10个人，因此利用一个10位的二进制数即可表示该状态。
实现代码：
Integer[][] memo; // 记忆数组
public int numberWays(List<List<Integer>> hats) {
int maxBit=0; // 按照人数，计算出一个最大的二进制数
for(int i=0;i<hats.size();i++){
maxBit+= (1<<i);
}
// 初始化记忆数组
memo=new Integer[41][maxBit+1];
// 将题目给出的每个人喜欢的帽子列表，转化为每顶帽子喜欢的人的列表
List<Integer>[] people = new List[41];
for(int i=0;i<hats.size();i++){
List<Integer> hatList=hats.get(i);
for(int j=0;j<hatList.size();j++){
if(people[hatList.get(j)]==null){
people[hatList.get(j)]=new ArrayList<>();
}
people[hatList.get(j)].add(i);
}
}
// 递归求解
return help(people,0,0,maxBit);
}
int help(List<Integer>[] people, int index, int bit,int maxBit){
// 如果所有人都被选择，返回1
if(bit==maxBit) return 1;
// 递归完所有帽子，仍有人未被选择时，返回0。
if(index==41) return 0;
// 如果记忆数组中存在当前解，直接返回
if(memo[index][bit]!=null) return memo[index][bit];
// 取得当前帽子喜欢人的列表
List<Integer> peopleList = people[index];
// 当前帽子不选择任何人。
long res=help(people, index+1, bit,maxBit);
if(peopleList==null) return (int)res;
// 当前帽子循环选择每个他喜欢的人
for(int p : peopleList){
// 如果当前人已经被其他帽子选择，跳过
if(((bit>>p) & 1) == 1) continue;
// 选择当前人并递归至下一个帽子
res+=help(people,index+1, bit | (1<<p),maxBit);
}
// 将当前结果计入记忆数组
memo[index][bit]=(int)(res%1000000007);
return (int)(res%1000000007);
}本题解法执行时间22ms。
Runtime: 22 ms, faster than 71.40% of Java online submissions for Number of Ways to Wear Different Hats to Each Other.
Memory Usage: 39.7 MB, less than 100.00% of Java online submissions for Number of Ways to Wear Different Hats to Each Other.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1434-number-of-ways-to-wear-different-hats-to-each-other-解题思路分析/