动态规划的经典应用：
DAG中的最长路和最短路。DAG的最长路和最短路都可以用记忆化搜索和递推两种实现方式。打印解时，既可以根据d值重新计算出每一步的最优决策，也可以在动态规划时“顺便”，记录下每步的最优决策。
DAG最长(短)路的特殊性，有两种“对称”的状态定义方式
状态1：设d(i)为从i出发的最长路,则
状态2：设d(i)为从i介绍的最长路,则
动态规划的经典应用：
DAG中的最长路和最短路。DAG的最长路和最短路都可以用记忆化搜索和递推两种实现方式。打印解时，既可以根据d值重新计算出每一步的最优决策，也可以在动态规划时“顺便”，记录下每步的最优决策。
DAG最长(短)路的特殊性，有两种“对称”的状态定义方式
状态1：设d(i)为从i出发的最长路,则
状态2：设d(i)为从i介绍的最长路,则
本文标题：DAG上的动态规划「三」
本文链接：https://www.haomeiwen.com/subject/ufarsctx.html
网友评论