题目描述
给一个列表hats，元素hats[i]表示第i个人喜欢的帽子类型
需要你给每个人都带自己喜欢颜色的帽子，同时不能和其他人一样
求方案数量
提示：
- 帽子个数不大于40
- 人数不大于8
| f1-状态压缩+动态规划 |
基本分析
- 这里帽子个数不大于40，人数不大于8，考虑是帽子找人还是人找帽子？人少，肯定是帽子找人，用二进制的s表示当前的人被分配帽子的情况
- 怎么dp状态？dp[i][s]表示处理了前i个帽子，并且人戴上帽子状态为s时的方案数
- 怎么初始化dp状态和定义dp数组？dp[0][0]=1,表示处理前0个帽子，戴帽子的人的状态是0是，对应的方案数为1。人的状态从0-(1<<n)-1, 长度是1<<n; 帽子前面多加了个0，定义为0-最大帽子数量madid，即range(maxid+1)
- 怎么转移状态？
- 先遍历前i个帽子的维度，假如遍历到i
- 再遍历人戴帽子的状态s，考虑如果第i个帽子不分配给任何人，这里就有f[i][s] = f[i-1][s]
- 接着遍历到第i个帽子能选的人，这个人的需要j还有一定要求（枚举的mask的第j位需要是1），满足以上条件的时候可以进行转移，表示累加一个前i-1个帽子分配给(s ^ (1<<j))的结果。
- 最后怎么获取结果？帽子的维度取maxid，人状态的维度取(1<<n)-1
代码
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
n = len(hats)
mod = 10**9 + 7
max_id = max(max(ids) for ids in hats)
hat2p = defaultdict(list)
for i, lst in enumerate(hats):
for hat in lst:
hat2p[hat].append(i)
mask = 1<<n
f = [[0] * mask for _ in range(max_id+1)]
f[0][0] = 1
for i in range(1, max_id+1):
for s in range(mask):
f[i][s] = f[i-1][s]
for j in hat2p[i]:
if s & (1<<j):
f[i][s] += f[i-1][s ^ (1<<j)]
f[i][s] %= mod
return f[-1][-1]
复杂度
时间：\(假设帽子个数是m，时间复杂度是O(m*2^n)\)
空间：\(需要O（m）的空间存帽子到人的对应关系；需要O(m*2^n)空间存动态规划结果；考虑滚动时，可以把m压缩到2。\)
总结
- 这里需要考虑是帽子找人还是人找帽子
- 在状态设计时候，没有存每个人具体选了马哥帽子。因为在统计方案数的时候，只需要知道哪些帽子被选，哪些人已经选过帽子。
- 考虑f[0][0]=1的初值状态，以及定义dp数组时的维度。
| f2-状态压缩+记忆化搜索 |
基本分析
-
dfs具体怎么构造？
- 参数：i表示考虑第i顶帽子，s表示戴帽子的人的状态
- 退出条件：
- 如果s是(1<<n)-1，表示人都带上了，返回1
- 如果i是40，表示帽子带完了，返回0
- 递归逻辑：
- 不戴第i个帽子时候，ans = dfs（i+1， s）
- 如果戴，遍历找到可以戴的人j，并且这个人之前没带过帽子（s>>j &1 == 0）,累加这个人的结果ans== dfs（i+1，state | 1<<j）
- 返回条件 ans % mod
-
怎么预处理？求出帽子最大编号；求出帽子对应人的关系
-
怎么调用dfs?从第一个帽子i=1，s=0开始
代码
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
n = len(hats)
mod = 10**9 + 7
h2p = defaultdict(list)
for i, lst in enumerate(hats):
for hat in lst:
h2p[hat].append(i)
maxhid = max(max(ids) for ids in hats)
mask = 1<<n
@cache
def dfs(i, s):
if s == mask-1:
return 1
elif i > maxhid:
return 0
ans = dfs(i+1, s)
for j in h2p[i]:
# 这个人之前没有戴帽子
if s >>j & 1 == 0:
ans += dfs(i+1, s | 1<<j)
return ans % mod
return dfs(1, 0)
复杂度
时间：\(O(m*2^{n})\)
空间：待确认
总结
- 不用的题目用dp和记忆化的思考困难度不一样，这个用dp正面考虑能简单
- 用记忆化的时候，假设的是最后状态到底的时候知道结果
- 所以我们可以把dfs（i+1，s）当做已知的
- 在找人的时候也是先假设s在j位置是0，累加的及结果的时候是j位置是1