1494. Parallel Courses II¶
题目信息¶
- 题号:
1494
- 难度:
Hard
- 主题:
状态压缩、动态规划、拓扑依赖
- 原题:
- 重点:
每学期最多选
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 的顺序分别在三个学期完成。