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) - 12. 预处理每个人的技能掩码将每个人拥有的技能映射到req_skills中的位置生成一个整数掩码skillMask[i]。3. 动态规划定义设dp[mask] 达到技能集合mask所需的最少人数prev[mask] 达到mask时最后添加的人prevMask[mask] 添加最后一个人之前的状态状态转移对于每个人i掩码sm从任意状态mask转移到mask | smif dp[mask] 1 dp[mask | sm]: dp[mask | sm] dp[mask] 1 prev[mask | sm] i prevMask[mask | sm] mask4. 初始化和结果重建dp[0] 0其他dp[mask] INF从target开始通过prev和prevMask回溯得到团队成员代码实现importjava.util.*;classSolution{publicint[]smallestSufficientTeam(String[]req_skills,ListListStringpeople){intmreq_skills.length;intnpeople.size();// 1. 将技能映射到下标MapString,IntegerskillIndexnewHashMap();for(inti0;im;i){skillIndex.put(req_skills[i],i);}// 2. 计算每个人的技能掩码int[]skillMasknewint[n];for(inti0;in;i){intmask0;for(Stringskill:people.get(i)){if(skillIndex.containsKey(skill)){mask|(1skillIndex.get(skill));}}skillMask[i]mask;}// 3. DP 初始化inttarget(1m)-1;int[]dpnewint[1m];Arrays.fill(dp,Integer.MAX_VALUE/2);dp[0]0;int[]prevPersonnewint[1m];int[]prevMasknewint[1m];Arrays.fill(prevPerson,-1);// 4. 状态转移for(intmask0;masktarget;mask){if(dp[mask]Integer.MAX_VALUE/2)continue;for(inti0;in;i){intnewMaskmask|skillMask[i];if(dp[mask]1dp[newMask]){dp[newMask]dp[mask]1;prevPerson[newMask]i;prevMask[newMask]mask;}}}// 5. 回溯重建结果ListIntegerresultnewArrayList();intcurtarget;while(cur!0){intpersonprevPerson[cur];result.add(person);curprevMask[cur];}// 转换为 int[]int[]ansnewint[result.size()];for(inti0;ians.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 路径示例一种最优解mask000 - 加 person3 (mask011) - mask011 mask011 - 加 person2 (mask100) - mask111 (target)团队[3, 2]→ 即 person3javapython和 person2cpp优化版本剪枝可以提前去掉被其他人“包含”的人减少状态转移次数// 去除冗余人员如果 personA 的技能集合是 personB 的子集且 personB 覆盖更多// 但 personA 仍可能有用因为需要组合所以需要谨慎处理// 更常用的是直接 DP因为 m ≤ 16状态数 ≤ 65536n ≤ 60总复杂度 ~ 4e6完全可行复杂度分析时间复杂度O(n × 2^m)其中 m ≤ 16n ≤ 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 解法状态压缩用整数位掩码表示技能集合DP 定义dp[mask]表示达到 mask 所需最少人数转移枚举每个人更新可达状态回溯记录转移路径重建团队这种 DP 是解决小规模集合覆盖问题的标准方法适合技能数 ≤ 20 的场景。