1494. 并行课程 II

题目地址(1494. 并行课程 II)

https://leetcode-cn.com/problems/parallel-courses-ii/

题目描述

给你一个整数 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
所有先修关系都是不同的，也就是说 dependencies[i] != dependencies[j] 。
题目输入的图是个有向无环图。

前置知识

• 拓扑排序

• 位运算

• 动态规划

公司

• 暂无

思路

看了下 n 的取值范围是 [1, 15]，基本可以锁定为回溯或者状压 DP。

一般 20 以内都可以，具体的时间复杂度和数据规模的关系可从我的网站中的复杂度速查表中查看。

再比如 5289. 公平分发饼干 看下数据范围就大概知道很可能就是回溯或者状压 DP。

这道题是状压 DP，如果你对其不了解，可以看下我之前写的 状压 DP 是什么？这篇题解带你入门，这里一些细节不再赘述。

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

接下来，我们使用一个数组 studied 来表示已经学习的课程，其中 studied[i] 是一个布尔值，表示第 i 个课程是否已经学习。

假设我们的 studied 已经确认了，那么下一步我们可以继续学习哪些课程呢？这就需要用到前面的 hashmap 啦，不妨称其为 neighbors，neighbors 的 key 是课程 id，值是 studied 数组，含义是想学习课程 i 必须先把 studied 数组中为 true 的全部学了。那么如果 neighbors[j] 是当前已经学习的课程数组的子集，那么说明当前已经达到了学习课程 j 的条件。

我们可以不断枚举当前已经学习的课程数组 的值，并由此确定接下来可以学习的课程集合 sub。得到 sub 之后要做的就是枚举 sub 的子集啦。

如何枚举子集呢？

比如需要枚举一个集合 S 的所有子集，你会如何做？

1. 状态。我们可以用一个和 S 相同大小的数组 picked 记录每个数被选取的信息， 用 0 表示没有选取，用 1 表示选取。

比如 S 大小为 3， picked 数组 [1,1,0]，表示 S 中的第一项和第二项被选择（索引从 1 开始）。如果 S 的大小为 n，就需要用一个长度为 n 的数组来存储，那么就有 $2^n$ 种状态。

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

1. 不重不漏。

实际上，我们也可用另外一个数 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，因为这些数潜在都可能是 132 的子集。如果我枚举了一个数字 030，由于 0 小于等于 1，3 小于等于 3，0 小于等于 2，因此 030 是 132 的子集。而如果我枚举了一个数字 040，由于 4 大于 3，因此 040 不是 132 的子集。

1. 效率。

上面的枚举方法虽然也可保证不重不漏，但是却不是最优的，这里介绍一种更好的枚举方法。

具体做法就是$x_i$和 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 的最大的一个。直观来看就是倒序枚举除了所有非空子集。

对于有 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. 数据范围要合适，否则数字无法表示了。

2. 只能有两种状态，这样才可以用二进制位 0 和 1 进行模拟。

其实状态压缩没有什么神秘，只是 API 不一样罢了。

有了上面的铺垫就简单了。我们只需要枚举所有子集，对于每一个子集，我们考虑使用动态规划来转移状态。

定义 dp[studied] 为学习情况为 studied 的最少需要学期数。

那么转移方程为：

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

其中 studied 为当前的学习的课程，sub 为当前可以学习的课程的子集。其中 studied 和 sub 都是一个数字，每一位的 bit 为 0 表示无该课程，为 1 表示有该课程。

关键点

• 枚举

• 位运算的枚举子集优化

代码

• 语言支持：Python3

Python3 Code:

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]

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(2^n)$

• 空间复杂度：$O(2^n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。