什么问题适合使用动态规划来解决?
如果一个问题具有以下两个特征,那么就可能适合用动态规划来解决:
- 1. 该问题具有最优子结构
- 2. 子结构独立且重叠
如果一个问题的最优解包含着该问题的子问题的最优解,那么这个问题就具有最优子结构。拥有最优子结构特征的问题,就有可能用动态规划来解决(当然,也有可能用贪婪算法)。
在递归式中,一个问题的子问题,以及子子问题的解决,很可能会用到很多重复的子问题的解,如果每一次都重新计算,那么重复的计算量非常大的,在动态规划中,会将子问题的解记录下来,这样,再次遇到该子问题时,就可以直接用已经保存的解。
综上,用动态规划来解决问题,主要按以下步骤来进行:
- 1. 定义问题与子问题的空间,找出问题的最优解结构,这个结构中一般会包含子问题的最优解。如果是这样的话,就可列出最优解的递归式。并且一般也会知道这个递归式的起始条件。(如果没有起始条件,就无法求解递归式)
- 2. 得到递归式以后,分析子问题是否有很多相互重叠的情况,如果是的话,就考虑从底向上进行问题的解决,并把每一步得到的子问题的解都记录下来(以此来避免重复解决子问题)。并在这个过程中记录下子问题最优解的信息。最后把这些信息整理出来,就得到了原问题的最优解。
所以,动态规划,可以说是一种从顶向底来了解最优化问题的最优解结构,然后再从底向上来解决问题的方法。
动态规划解问题的难点就在于找最优解的递归结构。
后面我将做一些用动态规划解决问题的练习,并把相应的笔记帖上来。
分享到:
相关推荐
算法导论----算法经典书籍----不用我多做介绍了吧。算法导论----算法经典书籍----不用我多做介绍了吧。
算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar
计算机算法导论--教师手册 英文原版 计算机专业必读书
算法导论--编程中经典的经典,值得每一位程序员用心品读
算法导论第三版练习题15.2-2的C++实现方案
这是算法导论第二版后面的8.3-4习题答案,整理过后的
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
算法导论第15章-动态规划的课后习题参考答案,对于算法爱好者而言,是不错的参考资料。
算法导论的重点以及课后习题答案和思考题答案。是英文的
算法导论--Introduction.to.Algorithms
算法导论作业-->Introduction to algrithms:homework
MIT课程算法导论6-046JFall-2005
算法专项练习--线型动态规划.ppt
最近在研习算法导论,发现课后习题的精彩程度甚至不亚于正文,对于算法导论的爱好者而言,这是一份不错的参考资料
中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部
[算法导论].[Introduction.to.Algorithms].Thomas.H.Cormen.Ronald.L.Rivest.Charles.E.Leiserson.Clifford.Stein.文字版.pdf
算法导论 算法导论 算法导论 算法导论 算法导论 算法导论算法导论 算法导论 算法导论
算法导论是算法方面的入门方面的权威著作,通俗易懂,很容易让人理解
算法导论的讲义、习题答案,与公开课视频相对应(视频去网易公开课找),搭配视频一起学习,效果非常,强烈推荐!