LeeCode 1125 并集最小组合

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

public int[] smallestSufficientTeam1(String[] req_skills, List<List<String>> people) {//1、映射//需要0,1,2,3,4,5 项技能Map<String, Integer> map = new HashMap<>();for (int i = 0; i < req_skills.length; i++) {map.put(req_skills[i], i);}int havePeople = people.size();int havaSkill = req_skills.length;List<Integer>[] listDp = new List[1 << havaSkill];//listDp[i]表示完成i项技能所需的最少人数的集合listDp[0] = new ArrayList<>();//listDp[0] ,空的集合，表示只需要0个人完成//2、查看people[i]在dp[]贡献for (int i = 0; i < havePeople; i++) {int iHaveSkill = 0;//i people拥有的技能for (String skill : people.get(i)) {iHaveSkill |= (1 << map.get(skill));}System.out.println("i:"+i);System.out.println("people.get(i).size():"+people.get(i).size()+" cur_skill:"+iHaveSkill);// newHaveSkill = ihaveSkill | j// dp[newHaveSkill] = min(dp[j] + 1,dp[newHaveSkill])for (int j = 0; j < listDp.length; j++) {if (listDp[j] == null)continue;int newHaveSkill = j | iHaveSkill;if (listDp[newHaveSkill] == null || listDp[j].size() + 1 < listDp[newHaveSkill].size()){listDp[newHaveSkill] = new ArrayList<>(listDp[j]);listDp[newHaveSkill].add(i);}}}//        System.out.println("listDp[listDp.length-1]:"+listDp.length);int len = listDp[(1 << havaSkill)-1].size();int[] res = new int[len];for (int i = 0; i < len;i++){res[i] = listDp[(1 << havaSkill)-1].get(i);}return res;}

思路解析：

1、集合A中共有0，1，2，3，4，5...元素

2、子集1拥有0，1，2 ；子集2拥有3，5；子集3拥有3, 4, 5

3、问题转化，最少合并子集个数，组合成集合A

4、子集组合【0/1】【0/1】【0/1】，选择当前集合或者不选择当前集合

最大不过是1 1 1，长度

问题求解：dp[8]中元素最少的个数

已知dp[pre] ，现有集合中拥有x个元素 ，dp[x|pre] 添加当前元素后的集合

dp[x|pre] = dp[pre] +1 或者不变