1125. Smallest Sufficient Team

表示一个二进制集合.中第位是表示该集合包含标号是的技能

令表示要获得集合表示的技能的最小花费.也就是最少需要选多少人

假设技能个数是,那么要求的答案就是

对于状态转移方程:

假设当前第个人的技能集合是.我们就拿当前的技能集合

去更新每一个的值.

因为要记录最后所选的答案.所以拿一个数组维护一下

时间复杂度.是人的个数,是技能个数

ps:看了mike-meng大佬的题解.所以加了自己的见解

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string, int>  mp;
        int n = req_skills.size();
        for(int i = 0; i < n; ++i) mp[req_skills[i]] = i;
        vector<int> dp(1 << n, -1);
        vector<int> team[1 << n];
        dp[0] = 0; // 一个技能都没有的最小花费是0 
        for(int i = 0; i < people.size(); ++i){
            int now = 0;
            for(string s : people[i]){
                int x = mp[s];
                now |= (1 << x);
            }
            for(int j = 0; j < (1 << n); ++j){
                if(dp[j] >= 0){ // 当前集合计算过 
                    int x = now | j; // 要更新的集合 
                    if(dp[x] == -1 || dp[x] > dp[j]+1){ // 集合没有计算过,或者当前选择更优 
                        dp[x] = dp[j]+1;
                        team[x] = team[j];
                        team[x].push_back(i);
                    } 
                }
            }
        }
        return team[(1 << n)-1];
    }
};