动态规划DP副本.ppt

文档介绍：动态规划使用动态规划的条件1、最优子结构2、无后效性最优子结构最短路径:如果某条路径是起点到终点的最短路径,则起点到该路径上的每一点都是最短路径。(最长路径?)无后效性最短路径:当前选择任何一条边都不会影响以后选择其他边。有费用的最短路径:设经过任何一条边时都要耗费一定的费用,总费用一定的情况下,当前选择某一条特定的边可能导致某些其他的边无法被选择。动态规划解题的步骤1、找出最优子结构2、写出动态规划方程3、使用自底向上或者自顶向下的方法求解4、逆推求解动态规划的重点思路与方程程序模型线型动态规划特征:问题的数学模型表现为线型。通常的子结构划分方式:顺序、中分最长递减子序列给定数列a1、a2、…、an,求最长递减子序列。子结构划分:顺序。最优子结构?无后效性?动态规划方程变量的定义:ai::=数列的第i个数fi::=以ai结尾的最长递减子序列长度方程:fi=max{fk}+10<=k<i,ak>aiork=0f0=0Answer=max{fi}1<=i<=n要点小结动态规划方程要点:变量定义,方程递归形式,参数范围,初始条件。程序模型要点:初始条件->变量初始化|递归终止条件参数范围->循环变量范围&判断条件方程递归形式->赋值语句