状态压缩dp

有什么好说的,先打它一波暴力

const h = [];
let hh = 0;
let min = Number.MAX_SAFE_INTEGER;
const isOk = function (ii, rl, people) {
  const is = ii.toString(2);
  const pl = people.length;
  let n = 0;
  for (let i = 0, il = is.length; i < il; i++) {
    const ib = is[i];
    if (ib === '1') {
      ++n;
      people[pl - il + i].forEach(e => {
        hh |= 1 << h[e];
      });
    }
  }
  if (hh === (1 << rl) - 1) {
    if (n < min) {
      min = n;
      hh = 0;
      return ii;
    }
  }
  hh = 0
  return false;
}
const smallestSufficientTeam = function (req_skills, people) {
  const rl = req_skills.length, pl = people.length;
  const max = 1 << pl;
  let r, t;
  for (let i = 0; i < rl; i++) {
    h[req_skills[i]] = i;
  }
  for (let i = 1; i < max; i++) {
    t = isOk(i, rl, people);
    if (t) r = t;
  }
  const rr = [];
  r = r.toString(2).split('')
  for (let i = 0; i < r.length; i++) {
    const e = r[i];
    if (e === '1') {
      rr.push(pl - r.length + i)
    }
  }
  h = [];
  hh = 0;
  min = Number.MAX_SAFE_INTEGER;
  return rr
};

当然是超时了, 好接下来用 c++ 写状压 dp 的代码

#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
  vector<int> smallestSufficientTeam(vector<string> &req_skills, vector<vector<string>> &people)
  {
    map<int, vector<int>> res; // res[i] = {...v} 代表技能标志位为 i 的最少人数队列 v
    unordered_map<string, int> skills;
    int rl = req_skills.size();
    int pl = people.size();
    res[0] = {};
    for (auto k = res.begin(); k != res.end(); k++)
      {
        cout << k->first << endl;
       
      }
    for (int i = 0; i < rl; i++)
    {
      skills[req_skills[i]] = i; // 把技能对应成一个个的二进制标志位
    }

    for (int i = 0; i < pl; i++)
    {
      int current_skill = 0;
      for (int j = 0; j < people[i].size(); j++)
      {
        current_skill |= 1 << skills[people[i][j]];
      }
      for (auto k = res.begin(); k != res.end(); k++)
      {
        // cout << k->first << endl;
        int combination = k->first | current_skill;
        if (res.find(combination) == res.end() || res[combination].size() > 1 + res[k->first].size())
        {
          res[combination] = k->second;
          res[combination].push_back(i);
        }
      }
    }
    return res[(1 << rl) - 1];
  }
};