问题描述 链接到标题
1494. 并行课程 II (Hard)
给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xᵢ, yᵢ] 表示一个先修课的关系，也就是课程 xᵢ 必须在课程 yᵢ 之前上。同时你还有一个整数 k 。
在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
示例 1：
输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
输出：3
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，
第三个学期上课程 4 。
示例 2：
输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出：4
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课
程 1 ，第四学期上课程 5 。
示例 3：
输入：n = 11, relations = [], k = 2
输出：6
提示：
1 <= n <= 151 <= k <= n0 <= relations.length <= n * (n-1) / 2relations[i].length == 21 <= xᵢ, yᵢ <= nxᵢ != yᵢ- 所有先修关系都是不同的，也就是说
relations[i] != relations[j]。 - 题目输入的图是个有向无环图。
解题思路 链接到标题
本题很容易想到拓扑排序，然后基于拓扑排序进行贪心，但是这个做法是错的！本题实质上是个 NP-Hard 问题，只能暴力求解。
考虑状压 DP，其实很容易想到子问题。即先选择 $1, 2$，再选择 $3, 4, 5$（满足先修的要求）。用二进制数 $to$$study$ 表示当前要学习的课程的集合，用 $pre[j]$ 表示课程 $j$ 的先修课程的集合。那么递归函数即为 $dfs(to$$study, pre)$。
在本次递归中，我们先求出当前可以学习的课程的集合 $tmp$：
for (int i = 0; i < n; ++i) {
if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
// 说明 i 在 to_study 中 且 i 的先修课程已经学习过了（或者没有先修课程）
tmp = (tmp | (1 << i));
++cnt;
}
}
如果 $tmp$ 的课程个数 $cnt <= k$，那么直接学习集合 $tmp$ 的所有课程，否则枚举 $tmp$ 的子集 $i$，如果子集 $i$ 的课程个数 $m$ 满足 $m <= k$，那么就学习该子集，那么下次递归中待学习的课程就可以用 $to$_$study \oplus i$ 表示。
枚举子集的方法参见 位运算与集合
C++ 中统计二进制数的 $1$ 的个数的库函数为 __builtin_popcount(i)。
代码 链接到标题
class Solution {
public:
static auto dfs(int to_study, vector<int> &cach, int full, vector<int> &pre, int n, int k) -> int {
if (to_study == 0) {
return 0;
}
if (cach[to_study] != -1) {
return cach[to_study];
}
int studied = (to_study ^ full);
int cnt = 0; // 统计可以学习的课程数
int tmp = 0; // 本次递归要学习的课程
for (int i = 0; i < n; ++i) {
if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
// 说明 i 在 to_study 中 且 i 的先修课程已经学习过了（或者没有先修课程）
tmp = (tmp | (1 << i));
++cnt;
}
}
if (cnt <= k) {
cach[to_study] = dfs(to_study ^ tmp, cach, full, pre, n, k) + 1;
return cach[to_study];
// return dfs(to_study ^ tmp, cach, full, pre, n, k) + 1;
}
int res = INT_MAX;
for (int i = tmp; i != 0; i = (i - 1) & tmp) {
if (__builtin_popcount(i) <= k) {
res = min(res, dfs(to_study ^ i, cach, full, pre, n, k) + 1);
}
}
cach[to_study] = res;
return cach[to_study];
}
int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
// 合集 i 表示要修的课程
// 合集 j 是 i 的子集，且 pre(j)（表示 j 的先修课程）与 i 没有交集，并且 size(j) <= k
vector<int> pre(n);
for (auto &vec : relations) {
int x = vec[0] - 1, y = vec[1] - 1; // 下标选择从 0 到 n - 1
pre[y] = (pre[y] | (1 << x));
}
int full = (1 << n) - 1; // 全集
vector<int> cach(1 << n, -1);
return dfs(full, cach, full, pre, n, k);
}
};