# 1125. Smallest Sufficient Team
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/smallest-sufficient-team/
## 思路
dp的index的第i个bit代表req_skills i在不在当下的state里面
dp[i]表示达成当下state需要多少个人
所以dp[1<<n-1]就是满足所有req_skills的最少人数
但是怎么找到具体需要哪些人呢
就要在过程当中用memo记录 memo[i]就是那dp[i]个人
## Code

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Map<String, Integer> map = new HashMap<>();
        for(String skill:req_skills){
            map.put(skill, map.size());
        }
        int n = req_skills.length;
        int m = people.size();
        int[] dp = new int[1<<n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        List<List<Integer>> memo = new ArrayList<>();
        for(int i=0; i<(1<<n); i++){
            memo.add(new ArrayList<>());
        }
        dp[0] = 0;
        
        for(int i=0; i<m; i++){
            for(int j=0; j<(1<<n); j++){
                if(dp[j]==Integer.MAX_VALUE) continue;
                int next = getNext(people.get(i), j, map);
                if(dp[next]>dp[j]+1){
                    dp[next] = Math.min(dp[next], dp[j]+1);
                    memo.remove(next);
                    memo.add(next, new ArrayList<>(memo.get(j)));
                    memo.get(next).add(i);
                }
            }
        }
        List<Integer> res = memo.get((1<<n)-1);
        int[] ans = new int[res.size()];
        for(int i=0; i<res.size(); i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
    private int getNext(List<String> skills, int mask, Map<String, Integer> map){
        for(String skill:skills){
            int idx = map.get(skill);
            if(((mask>>idx)&1)==0) mask+=1<<idx;
        }
        return mask;
    }
}