1125-smallest-Sufficient-Team

• 2020 年 2 月 18 日
• 筆記

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