动态规划-状态压缩DP

zhilu   in 杭州

# 状态压缩DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

# 题目：

1125. 最小的必要团队 (opens new window)

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

# 状态定义:

dp[i] 表示满足技能集合为i的最小人数

i的范围[0,2^m], m为全部技能数

# 初始状态:

dp[0] = 0 不需要任何技能时，需要的人数为0

# 状态转移:

每多一个人，都需要检查全部状态是否会因此而变小

即，原状态dp[prev] 新状态dp[next]= min(dp[next],dp[prev]+1)

状态关联 next = prev | newSkill

# 结果

取dp[2^m-1] 即基本全部技能的最少人数


public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
    int n = req_skills.length;
    int m = people.size();

    int total = 1 << n;

    Map<String, Integer> index = new HashMap<>();
    for (int i = 0; i < n; i++) {
        index.put(req_skills[i], i);
    }
    int[] dp = new int[total];
    Arrays.fill(dp, m);
    dp[0] = 0;


    int[] prevSkill = new int[total];
    int[] prevPeople = new int[total];

    for (int i = 0; i < m; i++) {
        List<String> skills = people.get(i);
        int current = 0;
        for (String skill : skills) {
            current |= (1 << index.get(skill));
        }

        for (int prev = 0; prev < total; prev++) {
            int next = prev | current;
            if (dp[next] > dp[prev] + 1) {
                dp[next] = dp[prev] + 1;
                prevSkill[next] = prev;
                prevPeople[next] = i;
            }
        }
    }

    List<Integer> res = new ArrayList<>();
    int i = total - 1;
    while (i > 0) {
        res.add(prevPeople[i]);
        i = prevSkill[i];
    }

    return res.stream().mapToInt(x -> x).toArray();

}
题目：