最小的必要团队（状态压缩DP）

从 people 中选择一些元素（技能集合），这些技能集合的并集等于 reqSkills，要求选的元素个数尽量少。

这里出现这个并集说法是具有提示性质的，如何正确的表示其中的某一个状态呢？

容易想到的方法是类似与贪心的思路，维护一个最多的，被需要的技能的people，每次加入一个。但是这个方法并不好实现。

如果将问题尽可能的抽象出来，其实就是这个并集给出了一个提示，我们可以当成一个非常典型的状态压缩dp。这个问题可以考察的是 最佳方案是多少人，也可以是具体的方案数，甚至可以是最佳方案有多少种不同的。 有一点类似于背包问题了，但是并不完全。

对于循环方案，本题内外循环的顺序可以互换，一个是枚举压缩状态，一个是枚举people。 对于要求解的具体方案，有两个思路，一个维护一个vector每次添加进去正确的，另外一个就是维护一个类似 指引线索 的数组。

需要注意的是： 对于两种方案，需要思考清楚初始状态。追踪的方法里，dp[i] 表示的是最佳的方案解，不追踪的方法里，dp[i]表示最佳的方案下，实际的方案。用dp[i].size()隐含了最佳方案的含义。

// 提前处理好每个people的状态，然后外层状态，内层people。 使用路径追踪。
class Solution {
public:vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {int n = req_skills.size(), m = people.size();unordered_map<string, int> map;for (int i = 0;i<n;i++){map[req_skills[i]] = i;}int amx = 1<<n;vector<int> dp(amx,m); // 注意这里初始化为最大dp[0] = 0;vector<int> pre_people(amx,0);vector<int> pre_skils(amx,0);vector<int> p_sk;for(auto& p:people){int cur_p = 0;for(auto& s: p) cur_p |= 1<<map[s];p_sk.push_back(cur_p);}for(int cur = 0;cur<amx;cur++){for(int i = 0;i<m;i++){int next = p_sk[i] | cur;if(dp[cur]+1<dp[next]){dp[next] = dp[cur]+1;pre_people[next] = i;pre_skils[next] = cur;}}}vector<int> ans;int end = amx-1;while(end>0){ans.push_back(pre_people[end]);end = pre_skils[end];}return ans;}
};// 直接添加
class Solution {
public:vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {int n = req_skills.size(), m = people.size();unordered_map<string, int> map;for (int i = 0;i<n;i++){map[req_skills[i]] = i;}int amx = 1<<n;vector<vector<int>> dp(amx); for(int i = 0;i<m; i++){int cur = 0;for(auto& s: people[i]){cur |= 1<<map[s];}for(int prev = 0;prev<amx;prev++){if (prev > 0 && dp[prev].empty()){continue;}int next = prev | cur;if(next == prev) continue;if(dp[next].empty() || dp[next].size() > dp[prev].size()+1){dp[next] = dp[prev];dp[next].push_back(i);}}}return dp[amx-1];}
};