2050. 并行课程 III - Kotlin 拓扑排序+动态规划

Problem: 2050. 并行课程 III

思路

拓扑排序

拓扑排序的思路是基于广度优先搜索的一种变体

对每个节点设置一张出度表（记录指向的所有节点）和一张入度表（仅记录入度的数值本身），设置一个队列记录当前入度为0的点（已无其他前置课程的可选课程）

先将初始时所有入度为0的节点加入队列中，遍历队列，对于每个节点遍历其出度表，找到它指向的所有节点，令这些被指向节点的入度-1

当被指向的节点入度减少至0时，则将其加入队列中，循环遍历队列直至队列为空

动态规划

对于每个课程，我们知道，由于要修完其全部前置课程才能开始选修，其开始时间点等于所有前置课程的完成时间点的最大值，同时其完成时间点等于开始时间点加上选修该课程的耗时

考虑到边界情况：对于那些最开始就被加入队列的节点，其完成时间点就等于选修该课程的耗时本身

解题方法

将拓扑排序和DP的思想结合在一起，设dp[i]为课程i的完成时间点

每当我们遍历队列中的节点，并更新其指向的节点时，进行两步操作

• 更新其入度-1，当入度为0时将其加入队列

最后输出dp数组的最大值即可

总的来说只是拓扑排序的模板套上了思路比较简单的DP，难度在困难里算比较简单的题目

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun minimumTime(n: Int, relations: Array<IntArray>, time: IntArray): Int {
        val outCourse = Array(n) { ArrayList<Int>() }
        val inCourse = IntArray(n)
        val dp = IntArray(n) { 0 }
        val topoQueue: Deque<Int> = LinkedList()

        for (relation in relations) {
            outCourse[relation[0] - 1].add(relation[1] - 1)
            inCourse[relation[1] - 1]++
        }

        for ((index, value) in inCourse.withIndex()) {
            if (value == 0) {
                topoQueue.addLast(index)
                dp[index] = time[index]
            }
        }

        while (topoQueue.isNotEmpty()) {
            val prev = topoQueue.removeFirst()
            for (next in outCourse[prev]) {
                dp[next] = Math.max(dp[next], dp[prev] + time[next])
                inCourse[next]--

                if (inCourse[next] == 0) {
                    topoQueue.addLast(next)
                }
            }
        }

        return dp.max()!!
    }
}