Hard

题目描述

给你一个整数 n ，表示有 n 门课程，课程编号从 1 到 n 。同时给你一个数组 relations ，其中 relations[i] = [prevCoursei, nextCoursei] ，表示课程 prevCoursei 和课程 nextCoursei 之间的先修关系：课程 prevCoursei 必须在课程 nextCoursei 之前修完。同时给你一个整数 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 门课程。

提示：

  • 1 <= n <= 15
  • 1 <= k <= n
  • 0 <= relations.length <= n * (n-1) / 2
  • relations[i].length == 2
  • 1 <= prevCoursei, nextCoursei <= n
  • prevCoursei != nextCoursei
  • 所有先修关系对 [prevCoursei, nextCoursei] 都是不同的
  • 所给出的图是一个有向无环图

解题思路

这是一个典型的状态压缩动态规划问题，需要结合图论和位运算来解决。

核心思路

由于 n ≤ 15，我们可以用状态压缩 DP 来表示课程的完成状态。每个课程对应二进制表示中的一位，1 表示已完成，0 表示未完成。

算法步骤

  1. 预处理依赖关系：构建每门课程的前置课程掩码，即修某门课程需要完成的所有前置课程的集合。

  2. 状态定义：dp[mask] 表示完成状态为 mask 的课程所需的最少学期数。

  3. 状态转移：对于每个状态 mask，找出所有可以在当前学期修的课程（即前置课程都已完成的课程），然后从中选择不超过 k 门课程的所有可能组合，更新对应的新状态。

  4. 优化策略：每次都尽可能选择更多的课程（贪心思想），这样能更快达到目标状态。

关键技巧

  • 使用位运算快速判断课程依赖关系
  • 枚举子集来生成所有可能的课程组合
  • 用记忆化搜索或自底向上 DP 来避免重复计算

时间复杂度主要来源于状态数量（2^n）和每个状态的转移计算，由于 n 较小，这种方法是可行的。

代码实现

class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
        vector<int> prereq(n, 0);
        
        // 构建前置课程掩码
        for (auto& relation : relations) {
            int prev = relation[0] - 1;
            int next = relation[1] - 1;
            prereq[next] |= (1 << prev);
        }
        
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            
            // 找出可以修的课程
            int canTake = 0;
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i)) && (prereq[i] & mask) == prereq[i]) {
                    canTake |= (1 << i);
                }
            }
            
            // 枚举所有可能的课程组合（不超过k门）
            for (int subset = canTake; subset > 0; subset = (subset - 1) & canTake) {
                if (__builtin_popcount(subset) <= k) {
                    dp[mask | subset] = min(dp[mask | subset], dp[mask] + 1);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        prereq = [0] * n
        
        # 构建前置课程掩码
        for prev, next in relations:
            prereq[next - 1] |= (1 << (prev - 1))
        
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
                
            # 找出可以修的课程
            can_take = 0
            for i in range(n):
                if not (mask & (1 << i)) and (prereq[i] & mask) == prereq[i]:
                    can_take |= (1 << i)
            
            # 枚举所有可能的课程组合（不超过k门）
            subset = can_take
            while subset > 0:
                if bin(subset).count('1') <= k:
                    new_mask = mask | subset
                    dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
                subset = (subset - 1) & can_take
        
        return dp[(1 << n) - 1]

public class Solution {
    public int MinNumberOfSemesters(int n, int[][] relations, int k) {
        int[] prereq = new int[n];
        
        // 构建前置课程掩码
        foreach (var relation in relations) {
            int prev = relation[0] - 1;
            int next = relation[1] - 1;
            prereq[next] |= (1 << prev);
        }
        
        int[] dp = new int[1 << n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == int.MaxValue) continue;
            
            // 找出可以修的课程
            int canTake = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && (prereq[i] & mask) == prereq[i]) {
                    canTake |= (1 << i);
                }
            }
            
            // 枚举所有可能的课程组合（不超过k门）
            for (int subset = canTake; subset > 0; subset = (subset - 1) & canTake) {
                if (CountBits(subset) <= k) {
                    int newMask = mask | subset;
                    dp[newMask] = Math.Min(dp[newMask], dp[mask] + 1);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
    private int CountBits(int num) {
        int count = 0;
        while (num > 0) {
            count += num & 1;
            num >>= 1;
        }
        return count;
    }
}

var minNumberOfSemesters = function(n, relations, k) {
    const prereq = new Array(n).fill(0);
    
    // 构建前置课程掩码
    for (const [prev, next] of relations) {
        prereq[next - 1] |= (1 << (prev - 1));
    }
    
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(3^n)
空间复杂度O(2^n)

说明：

  • 时间复杂度：状态数为 2^n，对于每个状态需要枚举其所有可修课程的子集，最坏情况下子集数量为 2^n，所以总时间复杂度为 O(3^n)
  • 空间复杂度：需要存储 2^n 个状态的 DP 值，所以空间复杂度为 O(2^n)

相关题目