企业官网建设流程全解析

LeetCode 1494. 并行课程 II：状压 DP 与位运算枚举子集精讲

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文以 LeetCode 1494「并行课程 II」为切入点，系统讲解如何在课程先修关系约束下，利用状态压缩动态规划（状压 DP）计算上完所有课程所需的最少学期数。文中完整复现了本题的拓扑约束建模、可用课程求解、二进制子集枚举优化与 DP 状态转移全过程，并给出可直接运行的 Python3 实现。读完本文，你将掌握"小数据范围（n ≤ 20）题目如何通过状态压缩将集合问题转化为位运算问题"这一高频套路，并能够迁移到公平分发饼干、并行课程等同类题。

题目回顾与前置知识

题目描述

给你一个整数n表示某所大学里课程的数目，编号为1到n，数组dependencies中，dependencies[i] = [xi, yi]表示一个先修课的关系，也就是课程xi必须在课程yi之前上。同时你还有一个整数k。

在一个学期中，你最多可以同时上k门课，前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

示例 1：

输入：n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2 输出：3 解释：第一个学期上课程 2 和 3，第二个学期上课程 1，第三个学期上课程 4。

示例 2：

输入：n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2 输出：4 解释：第一学期上课程 2 和 3，第二学期上课程 4，第三学期上课程 1，第四学期上课程 5。

示例 3：

输入：n = 11, dependencies = [], k = 2 输出：6

提示：

• 1 <= n <= 15
• 1 <= k <= n
• 0 <= dependencies.length <= n * (n-1) / 2
• dependencies[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• 所有先修关系都是不同的
• 题目输入的图是一个有向无环图（DAG）

前置知识

• 拓扑排序
• 位运算
• 动态规划

关于拓扑排序，仓库中的 thinkings/graph.md 给出了精确定义：有向图的拓扑排序是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每条有向边 uv，u 在排序中都位于 v 之前；当且仅当图中没有有向环时（即有向无环图），才有可能进行拓扑排序。本题给出的图正是 DAG，因此"保证一定存在一种上完所有课的方式"。

第一步：从数据范围锁定算法——为什么是状压 DP

拿到题目首先要看数据范围。本题n的取值范围是[1, 15]，这基本可以锁定解法为回溯或状压 DP。

仓库中另一道同类题 1723. 找出完成所有工作的最短时间 的题解也印证了这一判断套路："回溯和状压 DP 很多时候会一起出现。这道题的数据范围提示我可能使用状压 DP，因此数据范围很小。通常这种情况，就是直接对数据范围很小的那个变量做状态压缩，用 n 位的数字来表示选取情况，并且一般 n 不会超过 20。"

一般经验是：数据规模在 20 以内时，指数级的状态空间是完全可以接受的，此时状态压缩（用整数的二进制位表示集合）便成为首选工具。本题 n ≤ 15，状态总数最多为 2^15 = 32768，DP 数组完全放得下。

补充说明：状压 DP 是动态规划的一个重要分支，仓库 thinkings/dynamic-programming.md 在"动态规划的基本类型"一节中明确将其单列，并指出它的核心思想就是用二进制位来编码集合状态。

第二步：建模——用邻接表存储先修依赖

首先，我们需要用一个数据结构来存储课程之间的依赖关系。不妨使用 hashmap，这样可以在 $O(1)$ 的时间获取到一个课程的所有前置课程。

记这个映射为neighbors：key 是课程 id，value 是"学习该课程前必须已经学完的课程集合"。若neighbors[j]是"当前已经学习的课程数组"的子集，则说明当前已经达到了学习课程j的条件。

由于我们使用位运算表达集合，neighbors的 value 直接用整数表示即可：其二进制位为 1 的位置代表对应的前置课程。这样，构建依赖关系只需要一行位运算：

for fr, to in dependencies: neighbors[to - 1] |= 1 << (fr - 1)

这里把课程的 1-based 编号统一转为 0-based（减 1），1 << (fr - 1)把课程fr映射为整数中的第fr - 1个二进制位。

接下来，我们使用一个数字studied来表示已经学习的课程集合：studied的第 i 个二进制位为 1 表示第 i 门课已经学习，为 0 表示尚未学习。

第三步：核心难点——用位运算高效枚举子集

确定当前已学课程后，我们要得到"当前可以学习的课程集合"can，然后需要枚举can的所有子集sub（每个子集代表这一个学期实际选修的课程组合，子集大小不能超过k）。如何枚举子集是本题的关键考点。

方法一：朴素枚举（O(4^n)）

状态表示。我们可以用一个和集合 S 相同大小的数组picked记录每个数被选取的信息，用 0 表示未选取、1 表示选取。例如 S 大小为 3 时，picked = [1,1,0]表示 S 中的第一项和第二项被选择。若 S 大小为 n，则需要长度为 n 的数组，共 $2^n$ 种状态。

由于数组的值不是 0 就是 1，满足二值性，更多时候我们会使用一个数字y 来表示状态而非数组：y 的二进制位对应picked数组中的一项。

不重不漏。我们也可以用另一个数 x 来模拟集合 S，问题就转化为两个数（x 和 y）的位运算。因为用 1 表示被选取、0 表示未选取：如果 x 对应位为 0，y 也只能是 0；而如果 x 对应位为 1，y 可能是 0 或 1。也就是说 y 一定小于等于 x，因此可以枚举所有小于等于 x 的数的二进制，并逐个判断其是否真的是 x 的子集。

令 n 为 x 的二进制位数，可以写出如下代码：

// 外层枚举所有小于等于 x 的数 ans = []; for (i = 1; i < 1 << n; i++) { if ((x | i) === x) ans.push(i); } // ans 就是所有非空子集

这种算法的复杂度大约是 $O(4^n)$，与 x 成正比，n 最多取到 12 左右。

这样做不重不漏吗？答案是肯定的。因为(x | i) === x正是"i 是 x 的子集"的充要条件；当然你也可以用与运算，即((x | i) & i) === i来表示 i 是 x 的子集。

如果二进制不好理解，可以转化为十进制理解：比如给你一个数 132，让你找 132 的子集，这里的子集定义为"当前位的数字是否小于等于原数字当前位的数字"。从 1 枚举到 132，若枚举到 030：0 ≤ 1、3 ≤ 3、0 ≤ 2，因此 030 是 132 的子集；而若枚举到 040：4 > 3，因此 040 不是 132 的子集。

方法二：二进制子集枚举优化（O(3^n)）

上面的枚举方法虽然保证不重不漏，却不是最优的。更高效的做法是利用i = (i - 1) & x快速跳到下一个子集：

ans = []; // 外层枚举所有小于等于 x 的数 for (i = x; i != 0; i = (i - 1) & x) { ans.push(i); } // ans 就是所有非空子集

算法的关键在于i = (i - 1) & x这个操作：先将 i 减 1，从而把 i 最右边的 1 变成 0，并把这位之后的所有 0 变成 1；再与 x 求与，就保证了结果是 x 的子集，并且一定是所有子集中小于 i 的最大的一个。直观来看，这就是在倒序枚举 x 的所有非空子集。

复杂度分析：对于有 n 个 1 的二进制数字，需要 $2^n$ 的时间复杂度；而有 n 个 1 的二进制数字有 $C(n,i)$ 个，所以总时间复杂度为 $\sum_{i=0}^{n} C(n,i)\times2^i$，大约是 $O(3^n)$。和朴素方法一样，这种算法的时间复杂度也与 x 成正比，但 n 最多可以取到 15 左右，正好覆盖本题范围。

使用位运算模拟集合有两个前提要求：

1. 数据范围要合适，否则数字无法表示（n 不能超过整数的二进制位宽）；
2. 只能有两种状态，这样才可以用二进制位 0 和 1 进行模拟。

其实状态压缩没有什么神秘，只是 API 不一样罢了。仓库题解 464. 我能赢吗 中有一段非常到位的论述：用 set 存储状态时，in操作符、add(n)、len()这些集合 API 都可以用位运算一一模拟——1 << a表示把数字 a 加入集合，判断某位是否为 1 用与运算即可。仓库题解 1178. 猜字谜 也强调："枚举二进制子集是一个常见的操作，竞赛中也不时出现"，并直接采用了"枚举 puzzle 的所有子集（二进制子集枚举）"的方案。

第四步：DP 状态定义与转移方程

有了子集枚举的铺垫，本题的主体就简单了：枚举所有已学状态，对每个状态求解当前可学课程集合，再枚举可学集合的子集作为本学期的选课方案，用动态规划转移状态。

定义状态：dp[studied]表示"学习情况为 studied（二进制位为 1 表示已学）时的最少学期数"。

初始化：dp[0] = 0，表示什么都不学需要 0 个学期；其余状态初始化为一个较大值（代码中用 n，因为最坏情况下每学期只学一门课也最多需要 n 个学期）。

转移方程：

# 含义为我们可以选择在这一学期学习 sub，或者选择在下一学期学习 sub # dp[studied | sub] 就是两种选择的较小值 dp[studied | sub] = min(dp[studied | sub], dp[studied] + 1)

其中studied为当前已学的课程集合，sub为当前可以学习的课程集合的子集（本学期实际选修的课程）。studied和sub都是一个数字，每一位 bit 为 0 表示无该课程，为 1 表示有该课程。

答案：dp[(1 << n) - 1]，即所有课程都学完（低 n 位全为 1）时所需的最少学期数。

状态转移的直观理解

dp[studied | sub]是对"已经上了 dp[studied] 个学期、现在再上一个学期并选修 sub 这批课程"这一方案的学期数统计。由于我们按学期逐步累加，且子集枚举保证了不重不漏，最终dp中记录的必然是从初始状态到目标状态的最短"学期路径"。

完整代码实现（Python3）

class Solution: def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int: neighbors = collections.defaultdict(int) dp = [n] * (1 << n) for fr, to in dependencies: neighbors[to - 1] |= 1 << (fr - 1) dp[0] = 0 # 表示什么都不学的情况需要 0 学期 for i in range(1 << n): can = 0 for j in range(n): if (i & neighbors[j]) == neighbors[j]: can |= 1 << j # 已经学过的不能学 can &= ~i sub = can while sub: # 可以学习 sub if bin(sub).count("1") <= k: dp[i | sub] = min(dp[i | sub], dp[i] + 1) sub = (sub - 1) & can # 快速跳到下一个子集（枚举子集优化） return dp[(1 << n) - 1]

代码逐段解读

1. 构建依赖：neighbors[to - 1] |= 1 << (fr - 1)将课程fr记入课程to的前置课程集合，位或运算天然支持"集合合并"。
2. 主循环：for i in range(1 << n)遍历所有已学状态（从空集到全集）。
3. 求解可学课程：对每一门课j，若(i & neighbors[j]) == neighbors[j]（即 j 的全部前置课程都已包含在 i 中），则 j 当前可学，将其置入can。
4. 剔除已学：can &= ~i保证本学期不重复学习已学课程。
5. 枚举子集：sub = can起始，while sub配合sub = (sub - 1) & can倒序枚举can的所有非空子集；仅当子集大小bin(sub).count("1") <= k（不超过每学期最多课程数）时才进行转移。
6. 状态转移：dp[i | sub] = min(dp[i | sub], dp[i] + 1)记录到达新状态的更优学期数。

复杂度分析

令 n 为课程数量：

• 时间复杂度：$O(2^n)$（外层遍历 2^n 个状态，内层子集枚举总代价为 $O(3^n)$，在本数据范围下可行）
• 空间复杂度：$O(2^n)$（dp 数组长度）

说明：题解给出的时间复杂度为 $O(2^n)$，指的是外层状态数为 $2^n$；若将内层"求解可学课程 + 枚举子集"也计入，实际开销为 $O(n \cdot 2^n + 3^n)$，在 n ≤ 15 时均可接受。

关键点总结

• 枚举：先枚举所有已学状态，再枚举"可学课程集合"的所有子集；
• 位运算的枚举子集优化：sub = (sub - 1) & x是倒序枚举 x 所有非空子集的标准写法，相比朴素枚举（$O(4^n)$）可将复杂度降至 $O(3^n)$；
• 状态压缩：用整数的二进制位表达"课程是否已学"这一集合信息，DP 数组下标直接就是状态本身，无需额外哈希结构；
• 数据范围先行：n ≤ 15 是本题采用状压 DP 的最强信号，这一判断方法在仓库多篇题解（如 1723、464、1178）中反复出现，属于竞赛与面试中的通用套路。

举一反三：同类题型与扩展阅读

掌握状压 DP 与位运算枚举子集后，可以进一步练习仓库中下列同套路题目：

• 464. 我能赢吗：n ≤ 20 的博弈类状态压缩，配合记忆化递归，题解详细对比了"用 set 存储状态"与"用位运算模拟集合 API"的差异；
• 1723. 找出完成所有工作的最短时间：同样的小数据范围（jobs 数量不超过 12），题解同时给出回溯与状压 DP 两种方法，并强调子集枚举优化的必要性；
• 1178. 猜字谜：将单词与谜面均压缩为二进制集合，核心是"word 字符集合是 puzzle 字符集合的子集"这一判断，与本题"前置课程集合是已学集合的子集"异曲同工。

理论基础方面，可以回到仓库的算法体系文档继续深入：

• 状压 DP 在 thinkings/dynamic-programming.md 的"动态规划的基本类型"中被单独列为一种重要题型；
• 拓扑排序的定义与构建方法（入度为 0 的节点逐步剥离）详见 thinkings/graph.md，课程先修类题目正是拓扑排序最典型的应用场景。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode