title
作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
- 例如，团队
team = [0, 1, 3]表示掌握技能分别为people[0]，people[1]，和people[3]的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。
示例 1：
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]
示例 2：
输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]
提示：
1 <= req_skills.length <= 161 <= req_skills[i].length <= 16req_skills[i]由小写英文字母组成req_skills中的所有字符串 互不相同1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j]由小写英文字母组成people[i]中的所有字符串 互不相同people[i]中的每个技能是req_skills中的技能- 题目数据保证「必要团队」一定存在
solution
class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
n = len(req_skills)
m = len(people)
inf = float('inf')
dp = [inf] * (1 << n)
team = [[] for _ in range(1 << n)]
dp[0] = 0
skillmap = {v: i for i, v in enumerate(req_skills)}
personskill = []
for i, l in enumerate(people):
val = 0
for v in l:
val |= (1 << skillmap[v])
personskill.append(val)
for i in range(1, m + 1):
v = personskill[i - 1]
for j in range((1 << n) - 1, -1, -1):
nextstate = j | v
if dp[j] + 1 < dp[nextstate]:
dp[nextstate] = dp[j] + 1
team[nextstate] = team[j] + [i - 1]
return team[(1 << n) - 1]