1494. 并行课程 II

LC每日一题，参考1494. 并行课程 II，难度分2082。

题目

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

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

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

输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
输出：3 
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。

输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出：4 
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。

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

解题思路

• 位集合+记忆化搜索：使用拓扑排序无法得到最小值,考虑其他方法.由于题目用例范围n<=16所以可以使用位集合表示所有课程,使用递归选哪些子集+记忆化搜索减少计算。

位集合+记忆化搜索

以下代码来自灵神.

class Solution {
    int[] pre1, memo;
    int k, u;

    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        this.k = k;
        pre1 = new int[n];
        for (int[] r : relations)
            pre1[r[1] - 1] |= 1 << (r[0] - 1); // r[1] 的先修课程集合，减1所以下标改从 0 开始

        u = (1 << n) - 1; // 全集 n个1
        memo = new int[1 << n];
        Arrays.fill(memo, -1); // -1 表示没有计算过
        return dfs(u);
    }

    int dfs(int i) {
        if (i == 0) return 0; // 空集 课上完了
        if (memo[i] != -1) return memo[i]; // 之前算过了
        int i1 = 0, ci = u ^ i; // i 的补集 表示已经上过的课
        for (int j = 0; j < pre1.length; j++)
            if ((i >> j & 1) > 0 && (pre1[j] | ci) == ci) //pre1[j]属于ci j没上过且j的前置课程都已上过可以学
                i1 |= 1 << j;
        if (Integer.bitCount(i1) <= k)  // 如果个数小于 k，则可以全部学习，不再枚举子集
            return memo[i] = dfs(i ^ i1) + 1;
        int res = Integer.MAX_VALUE;
        for (int j = i1; j > 0; j = (j - 1) & i1) // 枚举 i1 的子集 j
            if (Integer.bitCount(j) == k) //一次性最多学k个
                res = Math.min(res, dfs(i ^ j) + 1);
        return memo[i] = res;
    }
}

复杂度分析

• 时间复杂度：O(3^n)。
• 空间复杂度：O(n)。

2023.06.16