1494. Parallel Courses II

题目信息

题号:

1494

难度:

Hard

主题:

状态压缩、动态规划、拓扑依赖

原题:

LeetCode 1494

重点:

每学期最多选 k 门课程,且先修课必须在更早学期完成;求学完全部课程的最少学期数

题目重述

有 n 门课程,编号为 1 到 n。relations[i] = [prev,next] 表示课程 prev 是课程 next 的先修课。先修图保证无环。

每学期最多修读 k 门当前先修条件已经满足的课程。请返回完成全部课程所需的最少学期数。

1 <= n <= 15,1 <= k <= n,课程关系编号合法且无重复。

自建示例

无依赖的课程可以同学期并行完成:

输入:n = 3, relations = [[1,3],[2,3]], k = 2
输出:2
解释:第一学期同时学习课程 1 和 2,第二学期学习课程 3。

依赖链会限制并行能力:

输入:n = 3, relations = [[1,2],[2,3]], k = 3
输出:3
解释:课程必须按 1、2、3 的顺序分别在三个学期完成。