线性表

54-1-1
54-1-1
54-1-2
54-1-2
54-1-3
54-1-3
54-1-4
54-1-4

栈、队列、数组

54-2-1
54-2-1
54-2-2
54-2-2
54-2-3
54-2-3

树、二叉树

54-3-1
54-3-1
54-3-2.jpg
54-3-2.jpg
54-3-3.jpg
54-3-3.jpg
54-3-4.jpg
54-3-4.jpg
54-3-5.jpg
54-3-5.jpg

图

54-4-1
54-4-1
54-4-2
54-4-2
54-4-3
54-4-3
54-4-4
54-4-4
54-4-5
54-4-5
54-4-6
54-4-6
54-4-7
54-4-7
54-4-8
54-4-8
54-4-9
54-4-9

因为王道的算法太麻烦了，不利于人脑模拟算法执行，所以针对 AOE，我给出一个基于 DAG 上动态规划的算法。

定义 $S_i$ 为顶点 i 到终点的最长路径长度，则：

$$ S_i= \begin{cases} \underset{(i,j)\in E}{\overset{}{\mathrm{MAX}}}(S_j+\mathrm{len}(i,j)) & i \ne \mathrm{end} \\ 0 &i=\mathrm{end} \end{cases} $$

显然这个算法的时间复杂度是 $O(|E|)$ 的，代码递归地写就可以。

那么找出关键路径就很方便了：

54-4-9dot5
54-4-9dot5
54-4-10
54-4-10
54-4-11
54-4-11

查找

54-5-1
54-5-1
54-5-2
54-5-2
54-5-3
54-5-3
54-5-4
54-5-4
54-5-5
54-5-5
54-5-6
54-5-6
54-5-7
54-5-7

排序

54-6-1
54-6-1
54-6-2
54-6-2
54-6-3
54-6-3
54-6-4
54-6-4
54-6-5
54-6-5
54-6-6
54-6-6

运用快排的划分思想：

PDF在 Google Drive 打开

结课测试

PDF在 Google Drive 打开