LC.P1125[最小的必要团队]

方法一：状态压缩+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private long all;
    private int[] mask;
    private long[][] cache;

    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        int m = reqSkills.length;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < m; ++i) map.put(reqSkills[i], i);
        int n = people.size();
        mask = new int[n];
        for (int i = 0; i < n; ++i) {
            // 把 people[i] 压缩成一个二进制数 mask[i]
            for (String s : people.get(i)) {
                mask[i] |= 1 << map.get(s);
            }
        }
        int u = 1 << m;
        cache = new long[n][u];
        for (int i = 0; i < n; i++) Arrays.fill(cache[i], -1);
        all = (1L << n) - 1;
        long res = dfs(n - 1, u - 1);
        int[] ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; ++i) {
            if (((res >> i) & 1) > 0) ans[j++] = i;
        }
        return ans;
    }

    private long dfs(int i, int j) {
        if (j == 0) return 0;
        if (i < 0) return all;
        if (cache[i][j] != -1) return cache[i][j];
        long res = dfs(i - 1, j); // 不选 mask[i]
        long res2 = dfs(i - 1, j & ~mask[i]) | (1L << i); // 选 mask[i]
        return cache[i][j] = Long.bitCount(res) < Long.bitCount(res2) ? res : res2;
    }
}