表示一个二进制集合.
中第
位是
表示该集合包含标号是
的技能
令表示要获得集合
表示的技能的最小花费.也就是最少需要选多少人
假设技能个数是,那么要求的答案就是
对于状态转移方程:
假设当前第个人的技能集合是
.我们就拿当前的技能集合
去更新每一个
的值.
因为要记录最后所选的答案.所以拿一个数组维护一下
时间复杂度.
是人的个数,
是技能个数
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];
}
};
