DeepSeek LeetCode 1125.最小的必要团队 public int[] smallestSufficientTeam(String[] req_skills, List＜List

这是 LeetCode 1125 “最小的必要团队”问题。要求从候选人中选择一个最小的团队，使得团队成员的技能集合覆盖所有必需的技能。

问题理解

• 有一个技能需求列表req_skills，如["java", "python", "cpp"]
• 有people列表，people[i]是第i个人拥有的技能列表
• 目标是选出人数最少的团队，使团队掌握的技能集合包含所有req_skills
• 返回团队成员的下标数组（任意顺序），如果有多解，返回任意一个

难点：

• 技能数量最多 16 个（可状态压缩）
• 人数最多 60 人
• 需要找到最小覆盖，是一个集合覆盖问题的变种，但可以用状态压缩动态规划求解

核心思路

1. 状态压缩

由于req_skills长度 ≤ 16，可以用一个整数（mask）表示当前已掌握的技能集合：

• 第i位为 1 表示已掌握第i个技能
• 目标状态：target = (1 << m) - 1

2. 预处理每个人的技能掩码

将每个人拥有的技能映射到req_skills中的位置，生成一个整数掩码skillMask[i]。

3. 动态规划定义

设：

• dp[mask]= 达到技能集合mask所需的最少人数
• prev[mask]= 达到mask时最后添加的人
• prevMask[mask]= 添加最后一个人之前的状态

状态转移：
对于每个人i（掩码sm），从任意状态mask转移到mask | sm：

if dp[mask] + 1 < dp[mask | sm]: dp[mask | sm] = dp[mask] + 1 prev[mask | sm] = i prevMask[mask | sm] = mask

4. 初始化和结果重建

• dp[0] = 0，其他dp[mask] = INF
• 从target开始，通过prev和prevMask回溯得到团队成员

代码实现

importjava.util.*;classSolution{publicint[]smallestSufficientTeam(String[]req_skills,List<List<String>>people){intm=req_skills.length;intn=people.size();// 1. 将技能映射到下标Map<String,Integer>skillIndex=newHashMap<>();for(inti=0;i<m;i++){skillIndex.put(req_skills[i],i);}// 2. 计算每个人的技能掩码int[]skillMask=newint[n];for(inti=0;i<n;i++){intmask=0;for(Stringskill:people.get(i)){if(skillIndex.containsKey(skill)){mask|=(1<<skillIndex.get(skill));}}skillMask[i]=mask;}// 3. DP 初始化inttarget=(1<<m)-1;int[]dp=newint[1<<m];Arrays.fill(dp,Integer.MAX_VALUE/2);dp[0]=0;int[]prevPerson=newint[1<<m];int[]prevMask=newint[1<<m];Arrays.fill(prevPerson,-1);// 4. 状态转移for(intmask=0;mask<=target;mask++){if(dp[mask]==Integer.MAX_VALUE/2)continue;for(inti=0;i<n;i++){intnewMask=mask|skillMask[i];if(dp[mask]+1<dp[newMask]){dp[newMask]=dp[mask]+1;prevPerson[newMask]=i;prevMask[newMask]=mask;}}}// 5. 回溯重建结果List<Integer>result=newArrayList<>();intcur=target;while(cur!=0){intperson=prevPerson[cur];result.add(person);cur=prevMask[cur];}// 转换为 int[]int[]ans=newint[result.size()];for(inti=0;i<ans.length;i++){ans[i]=result.get(i);}returnans;}}

示例演示

输入：

req_skills = ["java", "python", "cpp"] people = [ ["java"], ["python"], ["cpp"], ["java", "python"], ["python", "cpp"], ["java", "cpp"], ["java", "python", "cpp"] ]

计算过程：

• 技能映射：java→0, python→1, cpp→2
• 技能掩码：
  • person0: 001 (1)
  • person1: 010 (2)
  • person2: 100 (4)
  • person3: 011 (3)
  • person4: 110 (6)
  • person5: 101 (5)
  • person6: 111 (7)

DP 路径示例（一种最优解）：

mask=000 -> 加 person3 (mask=011) -> mask=011 mask=011 -> 加 person2 (mask=100) -> mask=111 (target)

团队：[3, 2]→ 即 person3（java+python）和 person2（cpp）

优化版本（剪枝）

可以提前去掉被其他人“包含”的人，减少状态转移次数：

// 去除冗余人员：如果 personA 的技能集合是 personB 的子集，且 personB 覆盖更多// 但 personA 仍可能有用（因为需要组合），所以需要谨慎处理// 更常用的是直接 DP，因为 m ≤ 16，状态数 ≤ 65536，n ≤ 60，总复杂度 ~ 4e6，完全可行

复杂度分析

• 时间复杂度：O(n × 2^m)，其中 m ≤ 16，n ≤ 60，约 60 × 65536 ≈ 400 万次操作，完全可行
• 空间复杂度：O(2^m)，用于存储 dp 和回溯信息

为什么不能直接用贪心？

集合覆盖问题是 NP-hard 的，贪心算法（每次选覆盖最多未覆盖技能的人）不一定得到最优解（人数最少）。

例如：

• 技能[A,B,C]
• 人1:[A,B]
• 人2:[B,C]
• 人3:[A,C]

贪心会选择人1（覆盖2个），剩下C，需要人2或人3，总人数2；但最优解是人2+人3（覆盖全部）也是2，只是说明贪心可能无法保证最优。

总结

这道题是集合覆盖问题在技能数量有限（≤16）情况下的状态压缩 DP 解法：

1. 状态压缩：用整数位掩码表示技能集合
2. DP 定义：dp[mask]表示达到 mask 所需最少人数
3. 转移：枚举每个人，更新可达状态
4. 回溯：记录转移路径，重建团队

这种 DP 是解决小规模集合覆盖问题的标准方法，适合技能数 ≤ 20 的场景。