1125-smallest-Sufficient-Team

xiaohejun

发布于 2020-02-18 09:15:52

4050

发布于 2020-02-18 09:15:52

文章被收录于专栏：xiaohejun的算法知识分享

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

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

假设技能个数是$n$,那么要求的答案就是$dp[(1 << n)-1]$

对于状态转移方程:

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

$now$去更新每一个$dp[now|j], 0 <= j < (1 << n)$的值.

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

时间复杂度$O(m*2^n)$.$m$是人的个数,$n$是技能个数

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];
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-03-242，如有侵权请联系 cloudcommunity@tencent.com 删除