LeetCode 1494. 并行课程 II
题目描述
题意分析
每学期最多修
k门课，一门课的全部先修课都必须在此前学期完成，求修完所有课程的最少学期数。题目保证依赖图无环，而且课程数不超过15。当前能选的课超过容量时，不同组合会解锁不同的后续课程，不能任意挑选。课程数较少，可以枚举已修课程集合和本学期的选择，用动态规划比较所有必要方案。
解法：状态压缩 DP 枚举本学期课程
核心思路
[!blue]
用位掩码
mask表示已经完成的课程，第i位为1表示课程i+1已修完。pre[i]是第i+1门课的先修集合。只有该课不在mask中，并且(pre[i] & mask) == pre[i]，它才能加入本学期的可选集合available。前置条件只看旧mask，不能使用本学期新选的课。每学期只需要考虑选满当前能够选的数量，也就是
min(k, available 的大小)门。若某个完整安排本学期还有空位，却把一门现在就能修的课留到以后，可以把这门课提前到空位：它的前置已经完成，原来所在学期还会腾出位置，其后继也不会被延后。因此总学期数不会增加，总存在一个最优安排采用这种选择方式。所以可选课程不超过
k门时全部修完；超过k门时，只枚举恰好k门的组合。选满名额是安全剪枝，具体选哪几门却仍可能影响后续安排，必须比较各个子集。
dp[mask]记录按上述选择方式到达已修集合mask的最少学期数。未来能修什么只由已修集合决定，与此前顺序无关，因此到达同一集合的更慢方案可以丢弃。初始化dp[0] = 0，其余设为n+1；无环图总能按拓扑顺序每学期修一门，所以合法最终答案不会超过n。对当前选择的非空子集
subset，转移到next = mask | subset，用dp[mask]+1更新dp[next]。新选课程都不在旧集合中，next的整数值一定大于mask，所以按掩码从小到大遍历时，所有来源状态都会先于目标状态处理。当需要挑选
k门时，代码从subset = available开始，反复执行subset = (subset-1) & available。减一会清掉最低的一个1并打开更低位，再与available相与去掉不允许的位，从而按递减顺序遍历所有非空子集；只对其中置位数等于k的子集转移。最后读取全部课程都置位的状态。
解题步骤
- 将课程编号转成从
0开始的位编号，根据先修关系构造每门课的pre。- 建立
2^n个状态，只有空集合的学期数为0，其他状态初始化为n+1。- 按掩码递增遍历可达状态，找出所有未完成且前置齐全的课程。
- 可选数不超过
k时选全部，否则枚举其中恰好k门的子集，更新完成集合的最少学期数。- 返回
dp[(1<<n)-1]。没有可选课程的状态不再转移，完整集合也会在此结束。
代码实现
class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] pre = new int[n];
for (int[] r : relations) {
pre[r[1] - 1] |= 1 << (r[0] - 1);
}
int total = 1 << n;
int[] dp = new int[total];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for (int mask = 0; mask < total; mask++) {
if (dp[mask] == n + 1) {
continue;
}
int available = 0;
for (int i = 0; i < n; i++) {
// 只选尚未完成且全部前置已在旧集合中的课程。
if ((mask & (1 << i)) == 0 && (pre[i] & mask) == pre[i]) {
available |= 1 << i;
}
}
if (available == 0) {
continue;
}
// 容量足够就全部提前修完，不会阻碍后续课程。
if (Integer.bitCount(available) <= k) {
int next = mask | available;
dp[next] = Math.min(dp[next], dp[mask] + 1);
continue;
}
int subset = available;
while (subset > 0) {
if (Integer.bitCount(subset) == k) {
int next = mask | subset;
dp[next] = Math.min(dp[next], dp[mask] + 1);
}
// 枚举可选集合的子集，只转移其中恰好 k 门的方案。
subset = (subset - 1) & available;
}
}
return dp[total - 1];
}
}
func minNumberOfSemesters(n int, relations [][]int, k int) int {
pre := make([]int, n)
for _, r := range relations {
pre[r[1]-1] |= 1 << (r[0] - 1)
}
total := 1 << n
dp := make([]int, total)
for i := 0; i < total; i++ {
dp[i] = n + 1
}
dp[0] = 0
for mask := 0; mask < total; mask++ {
if dp[mask] == n+1 {
continue
}
available := 0
for i := 0; i < n; i++ {
// 只选尚未完成且全部前置已在旧集合中的课程。
if (mask&(1<<i)) == 0 && (pre[i]&mask) == pre[i] {
available |= 1 << i
}
}
if available == 0 {
continue
}
// 容量足够就全部提前修完，不会阻碍后续课程。
if bitsCount(available) <= k {
next := mask | available
if dp[mask]+1 < dp[next] {
dp[next] = dp[mask] + 1
}
continue
}
subset := available
for subset > 0 {
if bitsCount(subset) == k {
next := mask | subset
if dp[mask]+1 < dp[next] {
dp[next] = dp[mask] + 1
}
}
// 枚举可选集合的子集，只转移其中恰好 k 门的方案。
subset = (subset - 1) & available
}
}
return dp[total-1]
}
func bitsCount(x int) int {
count := 0
for x > 0 {
x &= x - 1
count++
}
return count
}
复杂度分析
- 时间复杂度：Java 为 $O(n2^n+3^n)$。每个状态检查
n门课；枚举已修集合与不相交选择子集时，每门课最多有“已修、本学期选、不选”三种归属，所以总枚举数以 $3^n$ 为上界。当前 Go 的bitsCount每次最多清除n个置位，因此其上界为 $O(n2^n+n3^n)$。- 空间复杂度：$O(2^n+n)$。保存状态表和每门课的先修掩码。
关键点总结
[!green]
- 必须保存课程集合，单纯的已修数量无法决定下一学期哪些课能选。
- 所有先修课都要在旧状态中完成，同一学期内不能沿依赖链连续解锁。
- 空余名额可以用当前可选课补满而不增加总学期数，但满额组合仍需要枚举。
- 每次转移都增加新课程，掩码递增顺序就是合法的状态处理顺序。
易错点总结
[!yellow]
- 只判断先修集合与
mask有交集，会把仅完成部分前置的课程误判为可选。- 构造可选集合时不断加入本学期新选课程，会让有先后依赖的课程被安排在同一学期。
- 可选数超过
k时随意挑选，会漏掉能更早解锁后续课程的组合。- 没排除已经修过的课程，会浪费名额，并让转移不再严格增加完成集合。
- 子集枚举忘记与
available相与，会带入不可选课程；计数应是置位数，而不是掩码数值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 210. 课程表 II | 中等 | 拓扑可用节点只是当前候选，有限并行容量下任意选k门不一定最优，需要比较候选子集。 |
| 1136. 并行课程 | 中等 | 原题每学期可并行所有就绪课程，本题增加每期最多k门的限制。 |