第3章动态规划1学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质,并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息,构造最优解。2通过应用范例学习动态规划算法设计策略。(1)矩阵连乘问题;(2)最长公共子序列;(3)最大子段和(4)凸多边形最优三角剖分;(5)多边形游戏;(6)图像压缩;(7)电路布线;(8)流水作业调度;(9)背包问题;(10)最优二叉搜索树。3数塔问题:有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大。4最短路径问题:地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,我们想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?5最短路径问题:6再看一例:最优子结构:如果ABEG是A到G的最短路径,那么ABE也是A到E的最短路径。78910
动态规划 来自淘豆网m.daumloan.com转载请标明出处.
