【经典题目】每个人戴不同帽子的方案数——从人对应物品到物品对应人的转换思路

from functools import lru_cacheclass Solution:def numberWays(self, hats: List[List[int]]) -> int:# 总人数n = len(hats)dic = collections.defaultdict(list)for i in range(n):for hat in hats[i]:dic[hat].append(i)@lru_cache(None)        def dp(cur, pos):# cur 代表当前轮到第cur顶帽子可供选择# pos 代表当前戴帽的人有哪些，为二进制压缩状态形式# 首先，如果当前所有人都带上了帽，则返回1if pos == (1<<n)-1:return 1# 若不满足所有人都戴上了帽，且当前也没有帽子了，则返回0if cur > 40:return 0# 首先考虑不戴该顶帽子，直接考虑后一顶，则其值应为dp(cur+1, pos)res = dp(cur+1, pos)# 考虑有人佩戴该顶帽子for i in range(n):# 找到喜欢该帽子的人，且这个人并没有戴其他帽子（即二进制pos中该位置为0）if i in dic[cur+1] and not pos&(1<<i):# 给这个人戴上帽子（该位置置1），并依序进行下去res += dp(cur+1, pos+(1<<i))return int(res%1000000007)return dp(0,0)

这道题目的本质其实还是dp，这是变成了带有备忘录体系的纯函数dp，多余这个子函数的两个输入输出其实是完全可以变成dp数组的两个维度的，对应的返回值其实解释dp数组应该存储的数值。

• 需要注意的是，位运算的级别好像很低，需要额外加上括号进行保护）

class Solution {public int numberWays(List<List<Integer>> hats) {final int MOD = 1000000007;int n = hats.size();// 找到帽子编号的最大值，这样我们只需要求出 f[maxhatid][2^n - 1] 作为答案int maxHatId = 0;for (int i = 0; i < n; ++i) {List<Integer> list = hats.get(i);for (int h: list) {maxHatId = Math.max(maxHatId, h);}}// 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划List<List<Integer>> hatToPerson = new ArrayList<List<Integer>>();for (int i = 0; i <= maxHatId; i++) {hatToPerson.add(new ArrayList<Integer>());}for (int i = 0; i < n; ++i) {List<Integer> list = hats.get(i);for (int h: list) {hatToPerson.get(h).add(i);}}int[][] f = new int[maxHatId + 1][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];List<Integer> list = hatToPerson.get(i);// 在喜欢这个帽子的用户里面选择for (int j: list) {// 当前这个位置有帽子了，因此可能是从前一个没有帽子的状态转移得到的if ((mask & (1 << j)) != 0) {f[i][mask] += f[i - 1][mask - (1 << j)];f[i][mask] %= MOD;}}}}return f[maxHatId][(1 << n) - 1];}
}

总结

这道题是一道状态压缩dp的思路，也就是需要根据之前的状态推出现在的可行状态。采用了二进制的方法来表示每个物品的两个状态还是很巧妙的。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！