LeetCode 1494. 并行课程 II

2022-05-05 HGNULB 约 12 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1494. 并行课程 II

题意分析

有 $n$ 门课（编号 $1$ 到 $n$），relations 给出若干条先修关系 $[x, y]$ 表示必须先修完 $x$ 才能修 $y$。每个学期最多修 $k$ 门课，且这学期要修的每门课的全部先修课都必须在此前的学期修完（同一学期内不能互为先修）。问最少多少个学期能修完全部课程；题目保证图无环，一定有解。

约束里最扎眼的是 $1 \le n \le 15$。这个数字几乎是在直说：用一个 $n$ 位二进制数表示「哪些课已经修完」，整个状态空间只有 $2^{15} = 32768$ 个，可以整体枚举。而 $k \le n$、relations 长度不超过 $n(n-1)/2$，都无关紧要——瓶颈完全在状态空间上。

更重要的是要识破一个陷阱：贪心地「每学期在可选课程里挑 $k$ 门」是错的。挑哪 $k$ 门会影响后续能解锁什么，一门看起来现在可修但没有后继的课，让位给一门解锁大量后继的课可能更优。而「哪门课解锁得多」这种局部指标也无法给出全局最优。这就排除了拓扑排序 + 贪心，逼向搜索或 DP。

边界要盯住两处：某个状态下可选课程数不足 $k$ 时，学期名额用不满，这是完全正常的；$k \ge n$ 且无任何先修关系时答案是 $1$。

解法：状态压缩 DP 枚举本学期课程

核心思路

暴力做法是逐学期搜索：当前已修集合下枚举所有大小不超过 $k$ 的可选子集，递归下去取最小学期数。同一个「已修集合」会从不同的修课顺序被重复到达（先修 A 再修 B 和先修 B 再修 A 得到同一集合），指数级重复计算是瓶颈。

突破口在于：未来还需要多少学期，只取决于「当前已修完哪些课」这一个集合，与这些课是按什么顺序、分几个学期修完的完全无关。这就是无后效性，于是「集合」可以直接当作 DP 的状态，把指数棵搜索树压成 $2^n$ 个状态。

显式写出状态定义：dp[mask] 表示把 mask 中所有位为 $1$ 的课程修完，最少需要几个学期。mask 的第 $i$ 位为 $1$ 表示课程 $i+1$ 已修完。初值 dp[0] = 0（一门不修需要零个学期），其余初始化为 $n + 1$ 这个不可能达到的值当作「未到达」标记（$n$ 门课最多 $n$ 个学期，所以 $n+1$ 一定是非法的）。答案是 dp[(1 << n) - 1]。

转移的对象是「本学期修哪些课」。给定状态 mask，一门课 $i$ 本学期可修的充要条件是两条：它自己还没修（mask 的第 $i$ 位为 $0$），且它的先修集合已被 mask 完全包含。把先修关系也压成位掩码 pre[i] 后，第二条就是一次按位与的判等 (pre[i] & mask) == pre[i]——这正是「集合包含」的位运算写法，也是状压 DP 里最常用的一招。把所有满足条件的课收集成 available。

接下来枚举本学期实际修的子集 subset ⊆ available，转移 dp[mask | subset] = min(dp[mask | subset], dp[mask] + 1)。这里有一个能省掉大量枚举的剪枝：若 available 的课程数不超过 $k$，直接一次性全修最优，不必枚举子集。理由是修课只会解锁更多课、绝不会关闭任何选项（先修条件是单调的），所以在名额够用时多修一门永远不亏——留着不修只会让状态更差或持平。反之当 available 超过 $k$ 时，必须枚举恰好 $k$ 门的子集：同样由单调性，名额不满用没有意义。

枚举一个集合的所有子集用经典写法 subset = (subset - 1) & available，从 available 自身开始递减，恰好不重不漏地遍历全部非空子集，总代价对所有 mask 求和是 $O(3^n)$。

解题步骤

先把先修关系压成位掩码数组 pre：对每条 $[x, y]$ 执行 pre[y-1] |= 1 << (x-1)。为什么按后继课归集：判断一门课能否修，问的是「它的所有先修是否齐了」，这是以被约束的课为主键的查询，所以要存「谁需要谁」而不是「谁解锁谁」。注意题目课程编号从 $1$ 起，位下标从 $0$ 起，两处都要减一。

开长度 $2^n$ 的 dp 数组，全部填 $n + 1$，再置 dp[0] = 0。用 $n+1$ 而不是 Integer.MAX_VALUE 当哨兵，是为了后面写 dp[mask] + 1 时不会溢出；同时 $n+1$ 严格大于任何合法答案，不会被误当成有效解。

按 mask 从小到大遍历所有状态。这个顺序是转移正确性的前提：任何转移都从 mask 走向 mask | subset，而 subset 非空意味着新状态的二进制值严格大于 mask，所以按数值升序遍历时，被更新的状态一定还没被处理过，符合拓扑序。

跳过 dp[mask] == n + 1 的状态。这些状态还没被任何路径到达（例如包含了某门课却不含其先修的非法集合），从它们出发转移会污染后续状态。

扫描 $n$ 门课算出 available：条件是 (mask & (1 << i)) == 0（尚未修）且 (pre[i] & mask) == pre[i]（先修齐备）。后者写成按位与判等，比逐条检查先修关系快得多。

available == 0 时 continue。要么全修完了（mask 是全集），要么这个状态是死路；无论哪种都无需转移。

bitCount(available) <= k 时直接把 available 整个并进去，一次转移完事。这一条是最关键的剪枝，避免了对小集合做 $2^{ available }$ 次无谓枚举；正确性来自「多修不亏」的单调性。

否则枚举 available 的所有子集，只对 bitCount(subset) == k 的做转移。用 subset = (subset - 1) & available 递减枚举，循环条件 subset > 0 保证不枚举空集（空集意味着一学期什么都不修，纯属浪费）。

返回 dp[total - 1]，即全集状态的最小学期数。题目保证无环所以必然可达，不会返回哨兵值。

以 n = 4、relations = [[2,1],[3,1],[1,4]]、k = 2 走一遍（课程 $1..4$ 对应位 $0..3$）：

建先修表：$[2,1]$ 使 pre[0] |= 1<<1，$[3,1]$ 使 pre[0] |= 1<<2，于是 pre[0] = 0b0110；$[1,4]$ 使 pre[3] = 0b0001；pre[1] = pre[2] = 0。
mask = 0b0000（dp = 0）：课程 2、3 无先修且未修，课程 1 的先修 0b0110 未满足，课程 4 的先修 0b0001 未满足，所以 available = 0b0110，位数 $2 \le k$，直接全修，dp[0b0110] = 1。
mask = 0b0110（dp = 1）：课程 1 的先修 0b0110 & 0b0110 == 0b0110 满足且未修；课程 4 的先修 0b0001 仍未满足。available = 0b0001，位数 $1 \le 2$，全修，dp[0b0111] = 2。
mask = 0b0111（dp = 2）：只剩课程 4，其先修 0b0001 已在 mask 中，available = 0b1000，全修，dp[0b1111] = 3。
其余 mask 要么值为 $5$（未到达）被跳过，要么产生不更优的转移。
返回 dp[0b1111] = 3。

顺带看看剪枝的效果：在 mask = 0 处若不做「不超过 $k$ 就全修」的判断，还要枚举 {2}、{3} 两个单元素子集并各产生一次转移，最终虽然也能得到 3，但状态图上多出了大量注定更差的分支。而当 available 有 5 门、$k = 2$ 时，恰好枚举 $\binom{5}{2} = 10$ 个子集是必须的——因为选哪两门确实会影响后续。

代码实现

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);
                }
                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
                }
            }
            subset = (subset - 1) & available
        }
    }

    return dp[total-1]
}

func bitsCount(x int) int {
    count := 0
    for x > 0 {
        x &= x - 1
        count++
    }
    return count
}

复杂度分析

时间复杂度：$O(2^n \cdot n + 3^n)$。外层遍历 $2^n$ 个状态，每个状态花 $O(n)$ 计算 available，这部分是 $2^n \cdot n \approx 5 \times 10^5$；子集枚举部分，对每个 mask 枚举其 available 的子集，所有状态求和的上界是 $\sum_{mask} 2^{ available(mask) } \le 3^n \approx 1.4 \times 10^7$（这是「枚举集合的子集」的经典求和结果，每个元素在「不在 mask、在 subset、都不在」三种情况中恰选一种）。$n = 15$ 时整体在千万级，可以接受。

空间复杂度：$O(2^n)$。dp 数组是 $2^{15} = 32768$ 个整数，约 $128$ KB；pre 只有 $n$ 个整数。没有递归，无额外栈开销。

关键点总结

看到 $n \le 20$ 左右且问题围绕「集合的选取」，先想状态压缩：用整数的二进制位表示集合成员，状态数 $2^n$ 可以整体枚举。$n \le 15$ 时甚至允许每个状态再做 $O(n)$ 或子集枚举。

集合运算的位运算对应关系要熟：包含判定是 (a & b) == a，并集是 |，差集是 a & ~b，元素个数是 bitCount，枚举子集是 sub = (sub - 1) & set。这套写法是状压 DP 的语法基础。

DP 状态必须满足无后效性。本题「未来所需学期数只取决于已修集合」是全部推导的地基；一旦状态里漏了会影响未来的信息（比如题目改成课程有不同学时），状态定义就要扩维。

单调性剪枝往往能砍掉大部分枚举：本题「修课只解锁不关闭」使得名额够用时全修必不劣，把小集合的 $2^m$ 次枚举压成 $1$ 次。做优化前先找这类「多做不亏」或「少做不亏」的性质。

按 mask 数值升序遍历天然满足转移的拓扑序，因为并上非空子集必然使数值变大。这一点让状压 DP 可以写成简单的正向递推而不需要显式排序或记忆化递归。

面试视角：面试官的第一道关卡是让你意识到贪心不对——要能主动举出「优先修解锁多的课」失效的直觉。第二道关卡是状态设计，要清楚说出 dp[mask] 的含义。第三道是复杂度，尤其要能解释子集枚举求和为什么是 $3^n$ 而不是 $4^n$。能顺带提出「不超过 $k$ 就全修」的剪枝，是明显的加分项。

易错点总结

先修掩码按错方向建：把 $[x, y]$ 写成 pre[r[0]-1] |= 1 << (r[1]-1)，n = 4, relations = [[2,1],[3,1],[1,4]], k = 2 时依赖关系整体反转，返回的学期数与正确答案 $3$ 不符。

课程编号忘记减一：写成 pre[r[1]] |= 1 << r[0]，n = 4 时会访问 pre[4] 直接数组越界。

包含判定写成 (pre[i] & mask) != 0：只要有一门先修修完就认为可修，n = 4, relations = [[2,1],[3,1]], k = 1 时课程 1 在只修完课程 2 后就被放行，返回的学期数偏小。

available 没有排除已修课程：漏掉 (mask & (1 << i)) == 0，mask | subset 与 mask 相同，dp[mask] 被自己加一更新，学期数无限增大或死循环式无效转移。

子集枚举写成 subset = (subset - 1) & mask（把 available 误写成 mask）：枚举出的子集全是已修课程，n = 4, k = 2 时任何状态都无法推进，返回哨兵值 $5$。

子集枚举循环条件写成 subset >= 0：subset = 0 时执行 (0 - 1) & available = available，回到起点无限循环。

只枚举子集而不做「不超过 $k$ 全修」的分支，且把条件写成 bitCount(subset) <= k：会额外产生大量「一学期少修几门」的转移，虽然结果仍正确，但 $n = 15$、$k = 15$ 时枚举量从 $2^n$ 暴涨到 $3^n$ 的满载，容易超时。

dp 初值用 Integer.MAX_VALUE：转移时 dp[mask] + 1 溢出成负数，负值会被 Math.min 当作更优解写入，最终返回一个负数。

不跳过未到达状态：dp[mask] == n + 1 时仍做转移，会把 $n+2$ 写进后继状态，哨兵语义被破坏，最终 dp[total-1] 可能是一个大于 $n$ 的假答案。

超过 $k$ 时用 bitCount(subset) <= k 而非 == k 且没有全修剪枝：结果正确但白跑一倍以上的转移；真正的错误版本是写成 >= k，k = 2 而 available 有 3 门时会把三门一起修进去，违反每学期最多 $k$ 门，返回值偏小。

返回 dp[total] 而非 dp[total - 1]：数组长度就是 total，直接越界。

相似题目

题目	难度	考察点
207. 课程表	中等	同为先修约束，但只判有无环，拓扑排序即可，无每学期名额限制
210. 课程表 II	中等	输出任意一个合法修课顺序，仍是拓扑排序，不涉及并行与最优化
1462. 课程表 IV	中等	查询任意两门课的可达性，用传递闭包或位集合的 Floyd 递推
698. 划分为k个相等的子集	中等	同为 $n$ 小的集合划分，状态是已用元素掩码，转移按「当前桶」而非「当前轮」
473. 火柴拼正方形	中等	上一题 $k = 4$ 的特例，可用记忆化搜索或状压，重点在剪枝顺序
847. 访问所有节点的最短路径	困难	状态是「已访问集合 + 当前所在点」的二元组，用 BFS 而非递推求最短
51. N 皇后	困难	用三个位掩码表示列与两条斜线的占用，是位运算表示约束的另一典型
630. 课程表 III	困难	课程带时长与截止期，$n$ 很大，改用堆做反悔贪心而非状压