数据结构与算法实习 算法之五:动态规划 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang lat]net. pku.edu.cn http://www.ipk.pku.edu.cn/pkuipk/course/siig/shixi/ 20118 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验教程》 (国家十一五规划教材),高教社2011年1月
数据结构与算法实习 ——算法之五：动态规划 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验教程》 （国家十一五规划教材），高教社2011年1月
引子 Ⅳloyd动态规划算法 自底向上,利用中间结果,迅速构造 ◎最优子结构、重复子结构、无后效性 o搜索中分支定界的特例 o空间换时间 o贪心法是动态规划的特例 ° Huffman树 ● Dijkstra算法 ●Prim算法, Kruskal算法
引子 Floyd动态规划算法 自底向上，利用中间结果，迅速构造 最优子结构、重复子结构、无后效性 搜索中分支定界的特例 空间换时间 贪心法是动态规划的特例 Huffman树 Dijkstra算法 Prim算法，Kruskal算法
内容 o动态规划的概念 o数字三角——递推、递归、备忘录 BestBsT构造 o动态规划与其他算法的比较
内容 动态规划的概念 数字三角——递推、递归、备忘录 BestBST构造 动态规划与其他算法的比较
什么是动态规划 动态规划( dynamic programming)是在上 世纪50年代由美国数学家贝尔曼( Richard Bellman)为研究最优控制问题而提出的 o在计算机科学界,动态规划成为一种通用的算法 设计技术用来求解多阶段决策的最优化问题
什么是动态规划 动态规划（dynamic programming）是在上 世纪50年代由美国数学家贝尔曼（Richard Bellman）为研究最优控制问题而提出的。 在计算机科学界，动态规划成为一种通用的算法 设计技术用来求解多阶段决策的最优化问题
动态规划法原理 动态规划法将待求解的问题分解成若干个子问题(这些子 问题间往往不是相互独立的) 将每个子问题只求解一次并将其解保存在一个表格中 o当需要再次求解此子问题时,只是简单地通过查表获得该 子问题的解,从而避免了大量的重复计算。 原问题 子问题1又子问题 子问题n 填表 匚原间题的解
动态规划法原理 动态规划法将待求解的问题分解成若干个子问题（这些子 问题间往往不是相互独立的） 将每个子问题只求解一次并将其解保存在一个表格中 当需要再次求解此子问题时，只是简单地通过查表获得该 子问题的解，从而避免了大量的重复计算。 原问题 子问题 子问题n 2 子问题1 填表 原问题的解