DP

DAG上的动态规划「三」

2019-08-18 本文已影响0人雨落八千里

动态规划的经典应用：

DAG中的最长路和最短路。DAG的最长路和最短路都可以用记忆化搜索和递推两种实现方式。打印解时，既可以根据d值重新计算出每一步的最优决策，也可以在动态规划时“顺便”，记录下每步的最优决策。

DAG最长(短)路的特殊性，有两种“对称”的状态定义方式
状态1：设d(i)为从i出发的最长路,则 $d(i)=max{(d(j)+1|(i,j)\in E}$
状态2：设d(i)为从i介绍的最长路,则 $d(i)=max{(d(j)+1|(j,i)\in E}$

上一篇下一篇

猜你喜欢

热点阅读