一句话理解
DAG DP：按拓扑序转移。
为什么要学
最长路、方案数。
讲解
f[v]=max(f[u]+w) 对边 u->v。入度为 0 的先算。
例子
最长路径在 DAG 上线性。一般图最长路难。
常见错误
- 有环当最长路 DP 死循环。
- 顺序不按拓扑。
第 400 课
DAG DP
🟠 进阶 约 10 分钟
练习 做完再看下一课
DAG 上最长路可以按拓扑 DP。
进度保存在本机浏览器里。
左右方向键也可翻课
第 400 课
DAG DP：按拓扑序转移。
最长路、方案数。
f[v]=max(f[u]+w) 对边 u->v。入度为 0 的先算。
最长路径在 DAG 上线性。一般图最长路难。
DAG 上最长路可以按拓扑 DP。
左右方向键也可翻课