1 题目
原题链接。
2 想法
题目实质上是一条拓扑排序的题，只不过，在拓扑排序的根底上，加上了一个工夫的限度。每门课程规定了须要肯定的工夫实现，也就是说，实现一门课程的工夫，须要依据先修课程确定。
拓扑排序能够应用广搜配合入度数组去解决，而计算某一门课程的工夫，须要依据先修工夫确定。能够必定的是，如果一门课程没有先修课程，那么修这门课程的工夫，就是time数组中的工夫。
而如果一门课程有先修课程，容易想到，须要依据最大的一门先修课程工夫去确定，比方课程3的先修课程是课程1和课程2，假如：
课程1须要破费的单位工夫为3课程2须要破费的单位工夫为5
那么，课程3须要破费的工夫就是max(课程1,课程2)+课程3的工夫，也就是取课程1和课程2最大值再加上修课程3的工夫。
这样，能够揣测，如果一门课程n+1有n门先修课程，那么修课程n+1的工夫，就是这修n门课程的最大值，再加上修课程n+1的工夫。这实际上就是一个简略的动静布局：
dp[n+1] = max(dp[0]..dp[n])+time[n+1]3 实现
代码有很具体的正文：
import java.util.*;public class Solution { public int minimumTime(int n, int[][] relations, int[] time) { // 工夫dp，留神存储的是dp[1]..dp[n] int[] dp = new int[n + 1]; // 存储入度，为了不便计算同样开了n+1 int[] inDegree = new int[n + 1]; // 邻接表 List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i <= n; i++) { list.add(new ArrayList<>()); } // 通过邻接表建图 for (int[] r : relations) { // 更新入度 ++inDegree[r[1]]; list.get(r[0]).add(r[1]); } // 广搜队列 LinkedList<Integer> queue = new LinkedList<>(); for (int i = 1; i <= n; i++) { // 如果入度为0 if (inDegree[i] == 0) { // 能够间接设置dp[i]的值，因为入度为0代表课程i没有先修课程 dp[i] = time[i - 1]; // 退出广搜队列 queue.addLast(i); } } // 广搜队列不为空 while (!queue.isEmpty()) { // 获取以后队列大小 int size = queue.size(); // 遍历以后队列中入度为0的课程 for (int i = 0; i < size; i++) { // 出队 int front = queue.pollFirst(); // 获取先修课程指向的是哪些课程 for (int v : list.get(front)) { // 课程v的工夫是dp[v]与先修课程front+修课程v的最大值 dp[v] = Math.max(dp[v], dp[front] + time[v - 1]); // 将课程v的入度减1，示意曾经实现一门课程 if (--inDegree[v] == 0) { // 如果入度为0，也就是先修课程全副实现，将其入队 queue.addLast(v); } } } } // 取最大值，不能间接dp[n]，因为最初修的课程不肯定是课程n，所以须要遍历一次，取所有dp的最大值 int res = 0; for (int v : dp) { res = Math.max(v, res); } return res; }}工夫与内存如下：
4 优化
4.1 队列优化
对于带队列的题目，一个常见的优化技巧是应用数组去模仿队列。
须要留神的是，这须要依据题目去确定，尽管队列中存储的是点，然而实际上存储的是边，因为每遍历到一个点就将对应的出边（的点）退出到队列中。察看题目边的范畴：
间接取这个范畴的队列即可，不会OOM：
int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)];留神因为n取值可能比拟大，导致n^2可能会爆int，所以须要做一下强制转换。
而后用两个变量代表队头和队尾：
int queueFront = 0;int queueTail = 0;// 入队queue[queueTail++] = i;// 出队i = queue[queueFront++];残缺代码（逻辑与下面一样，只是批改了队列局部）：
import java.util.*;public class Solution { public int minimumTime(int n, int[][] relations, int[] time) { int[] dp = new int[n + 1]; int[] inDegree = new int[n + 1]; List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i <= n; i++) { list.add(new ArrayList<>()); } for (int[] r : relations) { ++inDegree[r[1]]; list.get(r[0]).add(r[1]); } int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)]; int queueFront = 0; int queueTail = 0; for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) { dp[i] = time[i - 1]; // 入队 queue[queueTail++] = i; } } // 判断队列是否为空 while (queueFront < queueTail) { // 获取队列大小 int size = queueTail - queueFront; for (int i = 0; i < size; i++) { // 出队 int front = queue[queueFront++]; for (int v : list.get(front)) { dp[v] = Math.max(dp[v], dp[front] + time[v - 1]); if (--inDegree[v] == 0) { // 入队 queue[queueTail++] = v; } } } } int res = 0; for (int v : dp) { res = Math.max(v, res); } return res; }}工夫：
有一点点的优化，然而不多。
4.2 算法细节优化
开端能够看到有一处计算最大值的中央：
int res = 0;for (int v : dp) { res = Math.max(v, res);}为什么须要再次遍历dp计算最大值呢？
因为不晓得哪一个dp最大，然而，能够在每一次dp计算完结的时候，计算res：
import java.util.*;public class Solution { public int minimumTime(int n, int[][] relations, int[] time) { int[] dp = new int[n + 1]; int[] inDegree = new int[n + 1]; List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i <= n; i++) { list.add(new ArrayList<>()); } for (int[] r : relations) { ++inDegree[r[1]]; list.get(r[0]).add(r[1]); } int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)]; int queueFront = 0; int queueTail = 0; int res = 0; for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) { // 计算最大值 res = Math.max(res, time[i - 1]); dp[i] = time[i - 1]; queue[queueTail++] = i; } } while (queueFront < queueTail) { int size = queueTail - queueFront; for (int i = 0; i < size; i++) { int front = queue[queueFront++]; // dp[front]曾经确定是计算结束了，用dp[front]计算最大值 res = Math.max(res, dp[front]); for (int v : list.get(front)) { dp[v] = Math.max(dp[v], dp[front] + time[v - 1]); if (--inDegree[v] == 0) { queue[queueTail++] = v; } } } } return res; }}工夫：
貌似没影响，再持续优化一下。
4.3 建图优化
没错，就是应用链式前向星代替邻接表进行建图优化。
链式前向星介绍能够参考此处，不细说了。
最终代码：
import java.util.*;public class Solution { public int minimumTime(int n, int[][] relations, int[] time) { int[] dp = new int[n + 1]; int[] inDegree = new int[n + 1]; int[] last = new int[n + 1]; int edgeCount = relations.length; int[] pre = new int[edgeCount + 1]; // 初始化last为-1 Arrays.fill(last, -1); for (int i = 0; i < edgeCount; i++) { int v0 = relations[i][0]; int v1 = relations[i][1]; ++inDegree[v1]; // 建图 pre[i] = last[v0]; last[v0] = i; } int[] queue = new int[(int) Math.min(n * (n + 1L) / 2, 5L * 10_000)]; int queueFront = 0; int queueTail = 0; int res = 0; for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) { res = Math.max(res, time[i - 1]); dp[i] = time[i - 1]; queue[queueTail++] = i; } } while (queueFront < queueTail) { int size = queueTail - queueFront; for (int i = 0; i < size; i++) { int front = queue[queueFront++]; res = Math.max(res, dp[front]); // 遍历所有边 for (int lastEdge = last[front]; lastEdge != -1; lastEdge = pre[lastEdge]) { int v = relations[lastEdge][1]; dp[v] = Math.max(dp[v], dp[front] + time[v - 1]); if (--inDegree[v] == 0) { queue[queueTail++] = v; } } } } return res; }}工夫：
至此优化实现。
5 总结
题目以拓扑排序为根底，再其中退出了计算工夫的动静布局。
实现时，拓扑排序能够广搜+队列实现，计算工夫的dp是比较简单的一维dp，转移方程也比拟好推。
写代码时有些细节要留神：
- 数组调配
n+1而不是n - 因为一开始的算法不欠缺导致了计算实现
dp后还须要再遍历一次dp取最大值
优化次要依附链式前向星的工夫优化，队列优化以及算法细节优化成果并不显著。