新型动态程序设计.ppt

动态程序设计;基本原理;带权有向的多段图 ;概念;基本原理;机器分配 ;分析;最长不下降序列 ;分析;进一步;改进算法;凸多边形三角划分 ;分析;系统可靠性 ;分析;快餐问题 ;分析;优化;其他优化方法;石子合并 ;示例;贪心法 ;动态规划 ;积木游戏 ;积木游戏;分析;动态规划;免费馅饼 ;免费馅饼;分析;有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。 让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。 我们知道小球落在第i个格子中的概率pi= ，其中i为格子的编号，从左至右依次为0,1,...,n。 现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。;钉子和小球 ;分析;商店购物 ;商店购物;分析;状态转移方程;添括号问题 ;分析;最长前缀 ;最长前缀;分析;分析;多边形 ;样例;分析 ;分析;动态规划;进一步分析;进一步分析;最终？;完美解决;选课 ;选课;选课;样例分析;分析;改造树;动态规划;陨石的秘密 ;陨石的秘密;陨石的秘密;陨石的秘密;条件的简化 ;状态的表示;状态转移方程 ;状态转移方程;状态转移方程;小结;;;使用动态规划的条件;最优子结构;无后效性;动态规划解题的步骤;动态规划的重点;线型动态规划;最长递减子序列;动态规划方程;要点小结;矩阵乘法;动态规划方程;取数游戏;动态规划方程;最长公共子序列;动态规划方程;01背包;动态规划方程;环型动态规划;石子合并;动态规划方程;平面型动态规划;迷宫宝藏;动态规划方程;数字三角;字符串匹配;思路;字符串编辑距离