并行课程 II【LC1494】
给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi] 表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。
在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
今天的也好难呀
- 思路：拓扑排序【错误】
第一眼觉得是用拓扑排序做，将入度为0的节点放在队列中，队列中的所有节点都可以在同一学期上，因此把队列中的课程全部上完需要的学期数⌈ s i z e / k ⌉ 。但是WA了，原因该做法不是最优的，因为队列中的元素的后置课程的前置课程还没有全部完成，那么其的前置课程可以延期至下一轮再上
- 思路：状态压缩dp
- 子问题：
- 全集为U，我们需要解决的问题为上完所有的课程，最少需要多少个学期。
- 假设已经上了几门课程后，剩余的课程对应的集合为A，那么问题转变为上完集合A中所有的课程，最少需要多少个学期
- 这是一个和原问题相似的子问题，因此我们可以用递归/dp解决。
- 递归函数定义：定义dfs(i)为上完集合i所有的课程，最少需要多少个学期，此时补集Cui中的所有课程已经上完。dfs(U)即为答案。
- 状态转移：
由于每个学期最多上k门课，我们可以枚举i的大小不超过k的非空子集j（0 < ∣ j ∣ ≤ k）
优化：j中的每门课程的先修课一定在补集Cui中，因此可以求出先修课在补集Cui中的课程集合，记为i1。那么我们可以枚举i1的补集j，剩余课程为i∖j，那么可以得到转态转移方程为
dfs(i)=dfs(i∖j)+1
递归边界
i=0时，表示为空集，返回0
- 递归过程有重复调用，因此可以记录状态，当一个状态不是第一次遇到时，直接返回保存的结果
- 状态压缩/位运算：由于n小于等于15，因此可以使用状态压缩mask表示该课程是否在当前选课表中，mask的第i位表示当前选择第i门课。
- 位运算：
- 全集：当总共有15个状态时的全集，即集合大小为15，每位均为1
int size = 15; int ALL = (1 < < size) - 1;
- 补集：
ALL^A
集合A的补集 - 差集：B是A的子集，A^B即为集合A-集合B剩余的元素
- 判断B是否是A的子集：
(A & B) == B
如果一个集合B和另一个集合A的交集为它自身，那么B是A的子集 - 枚举A的子集
for (int j = A; j > 0; j = (j - 1) & A){ }
计算状态A中1的个数
int cnt = 0; for (int i = 0; i < size; i++){ if (A & (1 << i)) cnt++; }
实现
class Solution { public int minNumberOfSemesters(int n, int[][] relations, int k) { var pre1 = new int[n]; for (var r : relations) pre1[r[1] - 1] |= 1 << (r[0] - 1); // r[1] 的先修课程集合，下标改从 0 开始 int u = (1 << n) - 1; // 全集 var f = new int[1 << n]; f[0] = 0; for (int i = 1; i < 1 << n; i++) { int i1 = 0, ci = u ^ i; // i 的补集 for (int j = 0; j < n; j++) if ((i >> j & 1) > 0 && (pre1[j] | ci) == ci) // pre1[j] 在 i 的补集中，可以学（否则这学期一定不能学） i1 |= 1 << j; if (Integer.bitCount(i1) <= k) { // 如果个数小于 k，则可以全部学习，不再枚举子集 f[i] = f[i ^ i1] + 1; continue; } f[i] = Integer.MAX_VALUE; for (int j = i1; j > 0; j = (j - 1) & i1) // 枚举 i1 的子集 j if (Integer.bitCount(j) == k) f[i] = Math.min(f[i], f[i ^ j] + 1); } return f[u]; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/parallel-courses-ii/solutions/2310878/zi-ji-zhuang-ya-dpcong-ji-yi-hua-sou-suo-oxwd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
