# LeetCode: 1125. 最小的必要团队¶

## 1、题目描述¶

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]



输入：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 <= req_skills.length <= 16
• 1 <= people.length <= 60
• 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
• req_skills 和 people[i] 中的元素分别各不相同
• req_skills[i][j], people[i][j][k] 都由小写英文字母组成
• 本题保证「必要团队」一定存在

## 2、解题思路¶

• 使用动态规划
• 因为所有的技术不超过16种，因此按照一位对应一种技能，一共$2^{16}$就能表示所有的技能
• 设置一个dp数组，将所有的技能初始化为所有人
• dp[0]初始化为空
• 通过将当前人所拥有技能转化为位数据，进行判断
• 状态转换方程：
• d[x|y] = min(dp[x][y],dp[x]+dp[y])
• 不断地判断每个人的技能对当前所在技能产生的影响，如果加入这个人令技能增加，并且人数的增加小于1，更新人员列表

class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
length = len(req_skills)
mapping = {}
for i in range(length):
mapping[req_skills[i]] = i

dp = [list(range(len(people))) for _ in range(1 << length)]
dp[0] = []

for index, l in enumerate(people):
skill = 0
for s in l:
skill |= (1<<mapping[s])

for k, v in enumerate(dp):
n_skill = skill | k
if n_skill != k and len(dp[n_skill]) > len(v) + 1:
dp[n_skill] = v + [index]

return dp[(1 << length) - 1]