2050. 并行课程 III

题目描述

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCourse_j, nextCourse_j] ，表示课程 prevCourse_j 必须在课程 nextCourse_j 之前完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的月份数。

请你根据以下规则算出完成所有课程所需要的最少月份数：

如果一门课的所有先修课都已经完成，你可以在任意时间开始这门课程。
你可以同时上 任意门课程 。

请你返回完成所有课程所需要的最少月份数。

注意: 测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

示例 1:

输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
输出：8
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。你可以在月份 0 同时开始课程 1 和 2 。课程 1 花费 3 个月，课程 2 花费 2 个月。所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。

示例 2：

输入：n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
输出：12
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。你可以在月份 0 同时开始课程 1 ，2 和 3 。在月份 1，2 和 3 分别完成这三门课程。课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。

提示：

1 <= n <= 5 * 10⁴
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)
relations[j].length == 2
1 <= prevCourse_j, nextCourse_j <= n
prevCourse_j != nextCourse_j
所有的先修课程对 [prevCourse_j, nextCourse_j] 都是 互不相同 的。
time.length == n
1 <= time[i] <= 10⁴
先修课程图是一个有向无环图。

解法一：DFS + 记忆化搜索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


func max(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

func minimumTime(n int, relations [][]int, time []int) int {
    prevCourses := make(map[int][]int)
    for _, relation := range relations {
        prevCourses[relation[1]] = append(prevCourses[relation[1]], relation[0])
    }

    // minMonth[i] 记录完成第 i 门课需要的最少月份数
    minMonth := make([]int, n+1)
    ans := 0
    var dfs func(id int) int
    dfs = func(id int) int {
        if minMonth[id] == 0 {
            for _, prevCourseId := range prevCourses[id] {
                minMonth[id] = max(minMonth[id], dfs(prevCourseId))
            }
            minMonth[id] += time[id-1]
        }
        ans = max(ans, minMonth[id])
        return minMonth[id]
    }

    for i := 1; i <= n; i++ {
        dfs(i)
    }
    return ans
}