设g=（v，e）是节点为v_1，v_2，…，v_n的有向图，如果g具有以下性质，则称g是有序图。
每个边从索引较低的节点到索引较高的节点也就是说，每个有向边都具有i除v_n外，每个节点至少有一条边离开它。也就是说，对于每个节点vòi，至少有一个形状的边（vòi，vòj）。
给出了一个有效的算法，它取一个有序图g，并返回从vu 1开始到vu n结束的最长路径的长度。
如果你想看漂亮的乳胶版：here
我的尝试：
动态编程。Opt（i）=最大值{Opt（j）}+1对于所有的j，这样的j是可以从i得到的。
也许有更好的方法来做这件事吗我认为即使有了记忆，我的算法仍然是指数级的。（这是我在网上找到的一份旧的期中评估）
最佳答案
你的方法是对的，你必须这样做
Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i
但是，只有在运行时不使用备忘录，这才是指数型的。使用memoization，当您在节点i上时，您将拥有每个节点j，j>i的memoizated最优值。
对于最坏情况的复杂性，让我们假设每两个可以连接的节点都是连接的。这意味着，
v_1与(v_2, v_3, ... v_n)相连，v_i与(v_(i+1), v_(i+2), ... v_n)相连。顶点数（
V）=n因此，边数（
E）=n*(n+1)/2 = O(V^2)让我们把注意力集中在顶点上。对于这个顶点，我们必须遍历已经导出的
v_k节点的最优值。直接到达
(n-k)的途径数=（k-1）因此，最坏情况下的时间复杂度＝＞CC＞，这是幂2多项式的σ，因此将导致
v_k时间复杂度。简单地说，最坏情况的时间复杂度是
sigma((k-1)*(n-k)) from k=1 to k=n。