2050. 并行课程 III

题目

参考2050. 并行课程 III，难度分2084。

解题思路

• 记忆化搜索：动态规划：定义dp[i]表示完成课程i的最少月份，则结果为所有课程完成月份取最大值，转移方程为dp[i] = max(dp[in[i]]) + time[i-1]，即课程i所有前置课程的最大值 + 当前课程i所需月份，定义记忆化搜索函数dp减少重复计算。
• 拓扑排序+广度优先搜索：参考灵神题解，构建图的入度、出边集合可使用数组和列表，同一时刻学习完所有入度为零即前置课程学完的课程，更新相关出边的入度减一，如果入度为零加入队列等待下一次学习，最终队列为空则学完。

记忆化搜索

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        //一有没有先修课程（入度为0）的课程就开始学习，因为可以同时学习任意课程
        //构建图(HashMap或数组列表) 入度
        List<Integer>[] in = new List[n+1];
        for(int[] r : relations) {
            int pre = r[0], next = r[1];
            if(in[next] == null) in[next] = new ArrayList<Integer>();
            in[next].add(pre);
        }
        //动态规划思想 dp[i]表示学完课程i所需最少时间 
        //转移方程 dp[i] = max(dp[in[i]]) + time[i-1]//课程i的入度最少时间的最大值+课程i的时间
        //使用记忆化搜索 
        int ans = 0;
        int[] memo = new int[n+1];
        for(int i = 1; i <= n; i++) ans = Math.max(ans,dp(i, in, time, memo));
        return ans;
    }
    int dp(int i, List<Integer>[] in, int[] time, int[] memo) {
        if(in[i] == null || in[i].size() == 0) return time[i-1];
        if(memo[i] != 0) return memo[i];
        int cur = 0;
        for(int c : in[i]) {
            cur = Math.max(cur,dp(c, in, time, memo));
        }
        return memo[i] = cur + time[i-1];
    }
}

复杂度分析

• 时间复杂度：O(m+n)，m为课程前置关系数组relations长度，n为课程数。
• 空间复杂度：O(n)，入度数组和记忆化数组以及递归栈空间都为O(n)。

拓扑排序+广度优先搜索

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        var deg = new int[n];
        for (var r : relations) {
            int x = r[0] - 1, y = r[1] - 1;
            g[x].add(y);
            deg[y]++;
        }
        var q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++)
            if (deg[i] == 0)  q.add(i); // 没有先修课
        var f = new int[n];//定义f[i]表示完成第 i 门课程的最少月份数 (dp[i])
        int ans = 0;
        while (!q.isEmpty()) {
            int x = q.poll(); // x 出队，意味着 x 的所有先修课都上完了
            f[x] += time[x]; // 更新f[x] 加上当前课程的时间，就得到了最终的 f[x]
            ans = Math.max(ans, f[x]);//结果取最大
            for (int y : g[x]) { // 遍历 x 的邻居 y （出边）
                f[y] = Math.max(f[y], f[x]); // 更新 f[y] 的所有先修课程耗时的最大值 此时不用管time[y]
                if (--deg[y] == 0) q.add(y); // 入度为零加入队列
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(m+n)。
• 空间复杂度：O(n)。