leetcode：1125. 最小的必要团队【状压dp板子 + 集合覆盖板子】

分析

有一个集合
每个人其中一些点，选最少的人覆盖全集
一个点视作一位，考虑状压
dp[state]表示state的最少人选选法
一开始都是全选人，dp[0]是空
遍历每个人，看到每个人能覆盖的点
然后对于每一个state and v，如果加上这个人的点变成new_state
并且new_state大于state的话
如果new_state对应的人数要大于 v对应的人数+1
就可以更新
因为此时找到一个更小的方案

ac code

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # 集合覆盖问题
        # 状压dp问题
        # dp[state]表示state的最少人选选法
        
        n, m = len(req_skills), len(people)
        skill2index = {
    skill:i for i, skill in enumerate(req_skills)}
        dp = [list(range(m)) for _ in range(1 << n)] # 全选肯定可以达到要求
        dp[0] = [] # init

        # dp transfer
        for i, skills in enumerate(people):
            now_skills = 0 # 这个人的综合skills
            for skill in skills:
                now_skills |= 1 << skill2index[skill]
            #print(bin(now_skills))
            # every dp
            for state in range(1 << n):
                v = dp[state]
                new_state = state | now_skills # 加上这个人
                # 如果总技能变多，且该技能对应的人变少
                if new_state > state and len(dp[new_state]) > len(v) + 1:
                    #print(bin(new_state), v + [i])
                    dp[new_state] = v + [i]
        #print(dp)
        return dp[(1 << n) - 1]

总结

状压dp板子 + 集合覆盖板子