What is the core pattern used in Parallel Courses II?

The problem relies on state transition dynamic programming with bitmask representation to efficiently track completed courses and enforce prerequisites.

How do I determine which courses are available each semester?

Check the prerequisites of each course against the current bitmask state. Only courses with all prerequisites completed can be taken in the current semester.

Why is backtracking needed along with DP?

Backtracking through subsets of available courses allows exploring all valid combinations within the k-course limit while DP stores minimal semester counts for each state.

Can this approach handle n up to 15 efficiently?

Yes, using bitmask DP with subset enumeration keeps the solution feasible because 2^15 states are manageable for modern computation.

What happens if more than k courses are available?

The algorithm enumerates all subsets of size up to k to ensure the per-semester course limit is respected while still progressing optimally.

#1494

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

并行课程 II

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [x i , y i ] 表示一个先修课的关系，也就是课程 x i 必须在课程 y i 之前上。同时你还有一个整数 k 。在一个学期中，你最多可以同时上 k 门课，前…

动态规划位运算图位掩码

题目描述

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [x_i, y_i] 表示一个先修课的关系，也就是课程 x_i 必须在课程 y_i之前上。同时你还有一个整数 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 <= 15
1 <= k <= n
0 <= relations.length <= n * (n-1) / 2
relations[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。
题目输入的图是个有向无环图。

lightbulb

解题思路

方法一：状态压缩 + BFS + 子集枚举

我们用数组 $d[i]$ 表示课程 $i$ 的先修课程的集合。由于数据规模 $n\lt 15$ ，我们可以用一个整数的二进制位（状态压缩）来表示集合，其中第 $j$ 位为 $1$ 表示课程 $j$ 是课程 $i$ 的先修课程。

我们用一个状态变量 $cur$ 表示当前已经上过的课程的集合，初始时 $cur=0$ 。如果 $cur=2^{n+1}-2$ ，表示所有课程都上过了，返回当前学期即可。

如果课程 $i$ 的先修课程 $d[i]$ 的集合是 $cur$ 的子集，说明课程 $i$ 可以上。这样我们可以找到当前 $cur$ 状态的下一个状态 $nxt$ ，表示后续学期可以上的课程集合。

如果 $nxt$ 的二进制表示中 $1$ 的个数小于等于 $k$ ，说明后续学期可以上的课程数不超过 $k$ ，我们就可以将 $nxt$ 加入队列中。否则，说明后续学期可以上的课程数超过 $k$ ，那么我们就应该从后续可以上的课程中选择 $k$ 门课程，这样才能保证后续学期可以上的课程数不超过 $k$ 。我们可以枚举 $nxt$ 的所有子集，将子集加入队列中。

时间复杂度 $O(3^n)$ ，空间复杂度 $O(2^n)$ 。其中 $n$ 是题目给定的课程数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        d = [0] * (n + 1)
        for x, y in relations:
            d[y] |= 1 << x
        q = deque([(0, 0)])
        vis = {0}
        while q:
            cur, t = q.popleft()
            if cur == (1 << (n + 1)) - 2:
                return t
            nxt = 0
            for i in range(1, n + 1):
                if (cur & d[i]) == d[i]:
                    nxt |= 1 << i
            nxt ^= cur
            if nxt.bit_count() <= k:
                if (nxt | cur) not in vis:
                    vis.add(nxt | cur)
                    q.append((nxt | cur, t + 1))
            else:
                x = nxt
                while nxt:
                    if nxt.bit_count() == k and (nxt | cur) not in vis:
                        vis.add(nxt | cur)
                        q.append((nxt | cur, t + 1))
                    nxt = (nxt - 1) & x

speed

复杂度分析

指标	值
时间	complexity is O(n * 2^n * C(n, k)) due to iterating over all states and subsets of available courses, while space complexity is O(2^n) to store DP values for each state.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The problem expects a state transition dynamic programming solution using bitmask representation of course completion.
question_mark
Consider carefully which courses can be taken each semester based on prerequisites and k-course limits.
question_mark
Enumerating subsets efficiently and avoiding redundant DP updates demonstrates a strong grasp of the problem pattern.

warning

常见陷阱

外企场景

error
Failing to track prerequisites accurately can lead to invalid semester counts.
error
Not limiting course selection to k per semester can produce incorrect solutions.
error
Redundant state updates without pruning subsets increase runtime and memory usage unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change k dynamically each semester, requiring adaptive DP subset handling.
arrow_right_alt
Introduce weighted courses where semesters count differently based on course load.
arrow_right_alt
Allow optional courses with alternative prerequisites, increasing state complexity.

help

常见问题

外企场景

继续练习

#847 访问所有节点的最短路径 #1434 每个人戴不同帽子的方案数 #1595 连通两组点的最小成本