今天刷到了這樣一道題, 同時(shí)涉及了拓?fù)渑判蚝蛣?dòng)態(tài)規(guī)劃算法,記錄一下解題思路
題目如下

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

You may start taking a course at any time if the prerequisites are met.
Any number of courses can be taken at the same time.
Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

首先由于課程有互相依賴, 我們需要決定上課順序, 這部分使用拓?fù)渑判騺斫鉀Q
其主要思路是構(gòu)建入度表, 尋找當(dāng)前入度為0的課程,也就是前置課程已經(jīng)上完的課
在完成每一門課程后, 檢查它的后置課程的入度,如果也是0就加入課程列表

本題允許同時(shí)上無限門課故
狀態(tài)轉(zhuǎn)移方程: 完成dp[i]課程后的時(shí)間 = dp[i]課程話費(fèi)的時(shí)間 + max(dp[i]的前置課程最遲的一門的完成時(shí)間)

代碼如下

import collections


class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        # 入讀表
        indegree = [0] * n
        # 鄰接表
        adjacency = collections.defaultdict(list)
        # 逆鄰接表
        reversedAdjacency = collections.defaultdict(list)
        # 完成dp[i]課程后的時(shí)間
        # 狀態(tài)轉(zhuǎn)移方程: 完成dp[i]課程后的時(shí)間 = dp[i]課程話費(fèi)的時(shí)間 + max(dp[i]的前置課程最遲的一門的完成時(shí)間)
        dp = [0] * n
        # 初始化入讀表省容、鄰接表骂维、逆鄰接表(坐標(biāo)改為0開始的)
        for outNode, inNode in relations:
            indegree[inNode-1] += 1
            adjacency[outNode-1].append(inNode-1)
            reversedAdjacency[inNode-1].append(outNode-1)
        queue = collections.deque()

        # 尋找沒有前置課程的課程作為第一批學(xué)習(xí)的課程
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)
                # 對(duì)于入度為0的點(diǎn),即無前置課程的課程,完成的時(shí)間即課程所花費(fèi)的時(shí)間
                dp[i] = time[i]

        while queue:
            # 學(xué)習(xí)隊(duì)列中的課程
            course = queue.popleft()
            # 尋找前置課程中最后完成的一個(gè)
            pre_course_max = 0
            for pre_course in reversedAdjacency[course]:
                    pre_course_max = max(pre_course_max, dp[pre_course])
            # 根據(jù)狀態(tài)轉(zhuǎn)移方程更新這門課程的完成時(shí)間
            dp[course] = pre_course_max + time[course]
            # 找出已完成前置課程的課, 加入待學(xué)習(xí)課程隊(duì)列
            for c in adjacency[course]:
                indegree[c] -= 1
                if indegree[c] == 0:
                    queue.append(c)
        return max(dp)