RT，最近在看算导。我们都知道一般图上求解最长简单路径是 NP 的，但是在 DAG 上做 $s$ 到 $t$ 的最长简单路径是不是应该可以用动态规划的方法做到 $O(n+m)$ 的？

Link here 是一位大佬给的算导习题答案，他考虑从 $s$ 出发的每条出边，然后在去掉 $s$ 点的图 $G'$ 中求解子问题，是否没有这个必要？因为从 $s$ 出发无法回到 $s$。