动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。比较著名的应用实例有:求解最短路径问题,背包问题,项目管理,网络流优化等。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。
最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。
计算斐波那契数列的一个最基础的算法是,直接按照定义计算:
function fib(n)
if n = 0 or n = 1
return 1
return fib(n − 1) + fib(n − 2)
当n=5时,fib(5)的计算过程如下:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
由上面可以看出,这种算法对于相似的子问题进行了重复的计算,因此不是一种高效的算法。实际上,该算法的运算时间是指数级增长的。 改进的方法是,我们可以通过保存已经算出的子问题的解来避免重复计算:
array map [0...n] = { 0 => 0, 1 => 1 }
fib( n )
if ( map( n ) is cached )
return map( n )
return map( n ) = fib( n - 1 ) + fib( n - 2 )
将前n个已经算出的前n个数保存在数组map中,这样在后面的计算中可以直接易用前面的结果,从而避免了重复计算。算法的运算时间变为O(n)。
分享到:
相关推荐
技术环境除了要考察与企业所处领域直接相关的技术手段的发展变 化外,还应了解:国家对科技开发的投资和支持重点、技术转移和 技术商品化速度、专利及其保护情况、该领域发展动态和研究费用 总额等。 1.数据分析...
程序的动态性越强,内存管理就越重要,您的内存分配程序的选择也就更重要。让我们来了解可用于内存管理的不同方法,它们的好处与不足,以及它们最适用的情形。 回页首 C 风格的内存分配程序 C 编程...
这个问题考察了候选人的字符串处理能力,可以使用动态规划或KMP算法实现。 嵌入式系统软件开发相关问题 1. 什么是平衡二叉树?编写一个删除平衡二叉树的程序? 这个问题考察了候选人的数据结构知识,可以使用递归...
此外,本书开始用两章篇幅详细介绍了中英文面试的注意事项、常见问题及程序员的职业规划等软件工程师的常识。最后四章详细讲解了现在流行的智力测试题。 第一篇 求职 第1章 应聘求职 1.1 企业与人才 1.1.1 企业需要...
集流量收集、分析、报告于一体,回答谁(Who)在什么时间(When)、什么地方(Where)、执行什么行为(What)等用户最关心的问题。为全面了解企业的网络活动,合理有效分配和规划网络带宽提供科学的依据,从而保证企业的关键...
2,动态Cache 服务器 -- 52 美国Facebok.com,中国Yeejee.com,日本mixi.jp均采用开源分布式缓存服务器Memcache 52 3,图片缓存和加 52 memcached+squid+apache deflate解决网站大访问量问题 52 FeedBurner:...
程序的动态性越强,内存管理就越重要,您的内存分配程序的选择也就更重要。让我们来了解可用于内存管理的不同方法,它们的好处与不足,以及它们最适用的情形。 C 风格的内存分配程序 C 编程语言提供了两个函数来...
本资源是数学建模教材资源,包括线性规划,整数规划,非线性规划,动态规划,图与网络,排队论,对策论,层次分析法,插值与拟合, 数据的统计描述和分析,方差分析, 回归分析,微分方程建模等。
动态规划: 1011 NTA 简单题 1013 Great Equipment 简单题 1024 Calendar Game 简单题 1027 Human Gene Functions 简单题 1037 Gridland 简单题 1052 Algernon s Noxious Emissions 简单题 1409 ...
动态规划: 1011 NTA 简单题 1013 Great Equipment 简单题 1024 Calendar Game 简单题 1027 Human Gene Functions 简单题 1037 Gridland 简单题 1052 Algernon s Noxious Emissions 简单题 1409 ...
是否可以简化流程,减少用户操作步骤 (最好形成漏斗模型,规划合理访问路径) 用户习惯分析 平均使用时长 单次使用时长、日使用时长、周使用时长 可以进一步做渠道细分 平均启动次数 日、周、月启动次数 启动天数 周...
(最好形成漏斗模型,规划合理访问路径) 用户习惯分析 平均使用时长 单次使用时长、日使用时长、周使用时长 可以进一步做渠道细分 平均启动次数 日、周、月启动次数 启动天数 周、月游戏天数 使用间隔 平均...