最小的必要团队

这道题还算是比较经典的状压DP了，首先要注意的点是，这道题需要压缩两个状态，一个是学科，另一个是人选。这两个状态都小于16，首先对所有要求的学科进行映射，然后在对每个人求mask的时候根据映射求得一个状态值。这里可以分为两个解法，一种为查表法，一种为刷表法。查表法的基本思路就是一个01背包问题。对每个人，遍历所有的背包容量/科目状态，分为选或者不选。值得注意的是这里需要求当前背包状态去除当前人科目状态后的值需要用到&~这种操作。其余的就是基础的背包操作用dp[i]保存科目状态为i选人状态为dp[i]的值。每次更新查询当前选或不选的人数，选择人数少的。

code

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0 ; i < req_skills.length ; i ++){
            map.put(req_skills[i],i);
        }
        int n = 1<<req_skills.length;

        Long [] dp = new Long[n];
        Arrays.fill(dp, (1L<<people.size()) -1);
        dp[0] = 0L;
        for(int i = 0 ; i < people.size() ; i ++){
            int mask = 0;
            for(var k : people.get(i)){
                    mask|=(1<<map.get(k));
            }
            for(int j = n-1 ; j >= 0 ; j--){
                long res1 = (dp[j])|(1L<<i);
                long res2 = dp[j|mask];
                dp[j|mask] = Long.bitCount(res1)<Long.bitCount(res2)?res1:res2;
            }
        }
        long ans =dp[n-1];int i = 0;
        int [] temp = new int[Long.bitCount(ans)];
        int cur =0;
        while(ans!=0){
            if(ans%2==1){
                temp[cur++] = i;
            }
            ans/=2;
            i++;
        }
        return temp;
    }
}

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0 ; i < req_skills.length ; i ++){
            map.put(req_skills[i],i);
        }
        int n = 1<<req_skills.length;

        Long [] dp = new Long[n];
        Arrays.fill(dp, (1L<<people.size()) -1);
        dp[0] = 0L;
        for(int i = 0 ; i < people.size() ; i ++){
            int mask = 0;
            for(var k : people.get(i)){
                    mask|=(1<<map.get(k));
            }
            for(int j = n-1 ; j >= 0 ; j--){
                long res1 = (dp[j]);
                long res2 = (dp[j&(~mask)]|(1L<<i));
                dp[j] = Long.bitCount(res1)<Long.bitCount(res2)?res1:res2;
            }
        }
        long ans =dp[n-1];int i = 0;
        int [] temp = new int[Long.bitCount(ans)];
        int cur =0;
        while(ans!=0){
            if(ans%2==1){
                temp[cur++] = i;
            }
            ans/=2;
            i++;
        }
        return temp;
    }
}

刷表法的思路是从0开始遍历状态，并且对每个低级状态遍历所有mask，不断更新高级状态，这样当遍历到高级状态并且从未被更新过时，就可以直接跳过这个状态。这方法跟埃式筛的方法一模一样。

class Solution {
    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        var sid = new HashMap<String, Integer>();
        int m = reqSkills.length;
        for (int i = 0; i < m; ++i)
            sid.put(reqSkills[i], i); // 字符串映射到下标

        int n = people.size();
        var mask = new int[n];
        for (int i = 0; i < n; ++i)
            for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask[i]
                mask[i] |= 1 << sid.get(s);

        int u = 1 << m;
        var ids = new long[u]; // ids[j] 表示 f[j] 对应的 people 下标集合
        var f = new int[u]; // f[j] 表示并集为 j 至少要选的 people 个数
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int j = 0; j < u - 1; ++j) // f[u-1] 无需计算
            if (f[j] < Integer.MAX_VALUE)
                for (int i = 0; i < n; ++i)
                    if (f[j] + 1 < f[j | mask[i]]) {
                        f[j | mask[i]] = f[j] + 1; // 刷表：用 f[j] 去更新其它状态
                        ids[j | mask[i]] = ids[j] | (1L << i);
                    }

        long res = ids[u - 1];
        var ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; ++i)
            if (((res >> i) & 1) > 0)
                ans[j++] = i; // 所有在 res 中的下标
        return ans;
    }
}