并行课程 II

难度: Hard

给你一个整数 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] 。
题目输入的图是个有向无环图。

Submission

运行时间: 67 ms

内存: 16.2 MB

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:

        f = [0] * n
        for u, v in relations:
            f[v - 1] |= 1 << (u - 1)
        ans = n
        for _ in range(80):
            p = [i for i in range(n)]
            random.shuffle(p)
            s = (1 << n) - 1
            pans = 0
            while s:
                c = 0
                x = 0
                for j in p:
                    if (s >> j) % 2 and (f[j] & s) == 0 and c < k:
                        c += 1
                        x |= 1 << j
                s ^= x
                pans += 1
            ans = min(ans, pans)
        return ans

        pre1 = [0] * n
        for u,  v in relations:
            pre1[v - 1] |= 1 << (u - 1) 

        u = (1 << n) - 1
        f = [inf] * (1 << n)
        f[0] = 0
        for i in range(1, 1<< n):
            ci = u ^ i
            i1 = 0
            for j, p in enumerate(pre1):
                if i >> j & 1 and p | ci == ci:
                    i1 |= 1 << j
            if i1.bit_count() <= k:
                f[i] = f[i^i1] + 1
                continue
            j = i1
            while j :
                if j.bit_count() == k:
                    f[i] = min(f[i], f[i^j] + 1)
                j = (j - 1) & i1
        return f[-1]

Explain

该题解采用了状态压缩动态规划的思路。首先用一个整数表示每门课程的先修课状态，然后枚举所有可能的已上课程状态，对于每个状态，如果能找到一个不超过k门可上的先修课程组合，就可以推出这个状态的最少学期数。状态转移方程为f[i] = min(f[i], f[i^j] + 1)，其中i是当前状态，j是当前状态的一个不超过k门课的子集。最终答案为f[-1]，即全部课程都上完的状态所需的最少学期数。在此基础上，题解还用随机化算法进行了预处理，多次随机打乱课程顺序，计算需要的最少学期数，取最小值作为答案，以尽量逼近最优解。

时间复杂度: O(2^n * n^k)

空间复杂度: O(2^n)

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        # 随机算法预处理，进行80次尝试
        f = [0] * n
        for u, v in relations:
            f[v - 1] |= 1 << (u - 1)
        ans = n
        for _ in range(80):
            p = [i for i in range(n)]
            random.shuffle(p)
            s = (1 << n) - 1
            pans = 0
            while s:
                c = 0
                x = 0
                for j in p:
                    if (s >> j) % 2 and (f[j] & s) == 0 and c < k: # 检查课程j是否可上
                        c += 1
                        x |= 1 << j
                s ^= x
                pans += 1
            ans = min(ans, pans)
        
        # 动态规划主体
        pre1 = [0] * n
        for u,  v in relations: 
            pre1[v - 1] |= 1 << (u - 1) # 初始化pre1数组表示每门课的先修课状态

        u = (1 << n) - 1
        f = [inf] * (1 << n) # DP数组
        f[0] = 0
        for i in range(1, 1<< n): # 遍历所有状态
            ci = u ^ i
            i1 = 0
            for j, p in enumerate(pre1): # 检查状态i的哪些课程可以上
                if i >> j & 1 and p | ci == ci:
                    i1 |= 1 << j
            if i1.bit_count() <= k: # 如果可上课程数不超过k，直接转移
                f[i] = f[i^i1] + 1
                continue
            j = i1
            while j : # 枚举i1的所有不超过k门课的子集j
                if j.bit_count() == k: 
                    f[i] = min(f[i], f[i^j] + 1)
                j = (j - 1) & i1
        return f[-1]

Explore

在状态压缩动态规划中，使用整数来表示状态是为了利用位运算的高效性，简化状态的存储与转移。每个位代表一门课程是否已经完成，例如，一个整数中的第i位为1则表示第i门课程已完成。这样，课程的先修条件可以通过整数的位与操作来检查，若课程A的先修课为B和C，则只需检查表示状态的整数中B和C对应的位是否为1。这种方法能有效地处理状态的转移和检查，使得算法在处理大量数据时仍保持高效。

随机化算法中进行80次尝试是一个经验性选择，旨在在算法的准确性和效率之间找到一个平衡点。通过多次随机打乱课程顺序并计算每种情况下的最少学期数，可以增加找到接近最优解的机会。选择80次是基于算法的执行时间和结果稳定性的考虑；较多的尝试次数通常能提高结果的准确性，但同时也会增加算法的运行时间。这个数字可能根据实际问题的规模和复杂度进行调整，以达到最佳的性能。

在状态转移方程中，`i^j`表示的是位异或操作，用来从当前状态i中移除已经选择上课的子集j。具体来说，如果i表示当前的课程状态（哪些课已完成），而j是在当前状态下可以选择上的课程集合的子集，那么`i^j`将会生成一个新的状态，表示在上完j集合中的课程后剩余的课程状态。这种操作可以帮助算法从当前状态转移到新的状态，且每次状态转移都对应于一个学期的课程安排。通过这种方式，动态规划算法可以逐步构建出完成所有课程所需的最小学期数。