动态规划算法应用及其在时间效率上的优化
|
摘要
算法设计是软件设计的灵魂内容,动态规划作为相对成熟的算法设计技术,不断地被运用到工农业生产、经济、军事、工程技术等很多方面,显示出其高效、实用的性能和宽阔的应用前景。本文对动态规划所涉及的诸多方面进行了深入的研究,通过大量的程序设计实例阐述了包括动态规划的理论基础、实际应用、优化方法在内的几大方面的问题。具体包括:
一、从动态规划的本质入手,介绍了多阶段决策问题、阶段与状态、决策与策略、最优化原理与无后效性、最优指标函数和规划方程等一些专有名词的定义;利用一些常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特点;通过与一些常见算法的比较,讲解了动态规划与这些算法的区别和联系,突出了使用动态规划时的最优化、高效率和高消费等特性。
二、从三个具体问题的解决过程中可以看出,动态规划是必不可少的有力工具。通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现过程和思考方法,体现出在应用中相应的实践指导意义。
三、鉴于动态规划在简单设计后还存在很大的时间冗余,从构成其时间复杂度的三个方面:状态总数、每个状态转移的状态数、每次状态转移的时间进行优化,使得动态规划在时间效率上得到了进一步的提升,以期面对并解决更大数据规模的问题。不仅给出了优化的理论依据和具体方法,而且还给出了五个引用实例在优化前后的实验运行对比结果。
最后,总结全文,分析了动态规划的应用和优化在面对不同问题时需要进一步完善的地方,并指出了今后工作的研究方向。
The design of the algorithm is the main content of software design. As a mature technique of algorithm design, dynamic programming is widely used in industry, agriculture, economy, military, engineering and some other fields, which indicates that it is efficient and practical and it has a bright future. The dissertation deals with many aspects of dynamic programming. By using many examples of programming, it gives a detailed explanation of dynamic programming's rationale, application and optimization method. The details listed as follows:
First, through the introduction of its essence, it introduces the definition of some terms such as multistage decision-making, stage and state, decision-making and strategy, optimality principle, non-aftereffect, optimal target function, programming equation and so on. By using some common examples, it gives a full description of the diversity, the pattern and the artifice of dynamic programming in designing and application. By comparing with some common algorithms, it explains their differences and relationships and emphasizes its characteristics--- optimized, efficient, and consumptive.
Second, through solving three problems, we can find dynamic programming is a necessity. With the help of the following steps, like problem describing, sample analyzing, algorithm designing, problem solving and result testing, it gives a full explanation of the implementation process and thinking methods of dynamic programming in application. It also shows that dynamic programming is very useful and helpful in application.
Third, There is a time redundancy after dynamic programming is used to design algorithm simply, so I try to optimize the dynamic programming in three aspects of time complexity---total quantities of state, state quantities of every state transition and time of every state transition, which helps it improve a lot in time efficiency and makes it possible for the newly-- designed algorithm to solve the problem with large-sized data. Not only does it provide the theoretical basis and methods of optimization, but also it provides the comparison results of five experiments before it optimized and after it optimized.
In conclusion, the dissertation not only analyzes the improvements of the application and optimization of dynamic programming in solving other problems, but also points out the research direction of the work in the future.
一、从动态规划的本质入手,介绍了多阶段决策问题、阶段与状态、决策与策略、最优化原理与无后效性、最优指标函数和规划方程等一些专有名词的定义;利用一些常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特点;通过与一些常见算法的比较,讲解了动态规划与这些算法的区别和联系,突出了使用动态规划时的最优化、高效率和高消费等特性。
二、从三个具体问题的解决过程中可以看出,动态规划是必不可少的有力工具。通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现过程和思考方法,体现出在应用中相应的实践指导意义。
三、鉴于动态规划在简单设计后还存在很大的时间冗余,从构成其时间复杂度的三个方面:状态总数、每个状态转移的状态数、每次状态转移的时间进行优化,使得动态规划在时间效率上得到了进一步的提升,以期面对并解决更大数据规模的问题。不仅给出了优化的理论依据和具体方法,而且还给出了五个引用实例在优化前后的实验运行对比结果。
最后,总结全文,分析了动态规划的应用和优化在面对不同问题时需要进一步完善的地方,并指出了今后工作的研究方向。
The design of the algorithm is the main content of software design. As a mature technique of algorithm design, dynamic programming is widely used in industry, agriculture, economy, military, engineering and some other fields, which indicates that it is efficient and practical and it has a bright future. The dissertation deals with many aspects of dynamic programming. By using many examples of programming, it gives a detailed explanation of dynamic programming's rationale, application and optimization method. The details listed as follows:
First, through the introduction of its essence, it introduces the definition of some terms such as multistage decision-making, stage and state, decision-making and strategy, optimality principle, non-aftereffect, optimal target function, programming equation and so on. By using some common examples, it gives a full description of the diversity, the pattern and the artifice of dynamic programming in designing and application. By comparing with some common algorithms, it explains their differences and relationships and emphasizes its characteristics--- optimized, efficient, and consumptive.
Second, through solving three problems, we can find dynamic programming is a necessity. With the help of the following steps, like problem describing, sample analyzing, algorithm designing, problem solving and result testing, it gives a full explanation of the implementation process and thinking methods of dynamic programming in application. It also shows that dynamic programming is very useful and helpful in application.
Third, There is a time redundancy after dynamic programming is used to design algorithm simply, so I try to optimize the dynamic programming in three aspects of time complexity---total quantities of state, state quantities of every state transition and time of every state transition, which helps it improve a lot in time efficiency and makes it possible for the newly-- designed algorithm to solve the problem with large-sized data. Not only does it provide the theoretical basis and methods of optimization, but also it provides the comparison results of five experiments before it optimized and after it optimized.
In conclusion, the dissertation not only analyzes the improvements of the application and optimization of dynamic programming in solving other problems, but also points out the research direction of the work in the future.
引文
1 Richard Bellman.Dynamic Programming.Princeton University Press,1957
2 顾永清.试论城市的动态规划.城市规划汇刊.1994(1):40-43,65
3 常淑芬.动态规划及其在管理中的应用.华南金融研究.1997(2):71-75
4 赵奕,赵增墀,张隆昌,袁驰.动态规划在企业生产管理中的应用.纺织器材.1997(5):46-50
5 左志坚.动态规划在管理会计中的应用.西北大学学报(哲学社会科学版).1994(2):27-33
6 吴爱华,陶东兵,李承军.基于随机动态规划方法的水电站水库优化调度的研究与应用.广东水利水电.2003(1):27-29,32
7 吴爱华,周建中,陶东兵,李承军.水库优化调度中随机动态规划方法的研究与应用.计算机仿真.2003(10):41-44
8 侯增广,吴沧浦.一种基于动态规划策略的离散动态大系统递阶优化神经网络.自动化学报.1999(1):48-54
9 胡铁松,郭元裕.多目标动态规划的神经网络方法.电子学报.1999(10):71-73
10 黄西士,吴沧浦.精确求解-类动态规划问题的神经网络.控制与决策.1996(2):261-265,271
11 王彦保.离散系统最优控制中动态规划的神经网络算法.内蒙古科技与经济.2003(9):63-64
12 叶仲泉,张邦礼,曹长修.多层前馈神经网络的动态规划算法.重庆大学学报(自然科学版).1996(6):39-43
13 殷春霞,胡铁松,郭元裕.基于人工神经网络的多目标动态规划.武汉水利电力大学学报.1999(6):2-6
14 Thomas H.Cormen等著,潘金贵等译.算法导论.第1版.北京:机械工业出版社,2006
15 杜彦娟.利用动态规划数学模型求最短路径.煤炭技术.2005(1):97-98
16 施益昌,郑贤斌,李自力.基于MATLAB动态规划中最短路线的实现程序.电脑学习.2003(6):38-39
17 金锡万.库存决策中的动态规划法及其应用探索.华东冶金学院学报.1997(1):37-42
18 高雷阜.资源分配的多目标优化动态规划模型.辽宁工程技术大学学报(自然科学版).2001(5):122-124
19 卢志文.基于动态规划的资源分配算法.福建电脑.2005(2):77,74
20 宿洁,刘家壮.多阶段资产投资的动态规划决策模型.中国管理科学.2001(3):56- 62
21 张平.动态规划法在投资分配决策中的应用.税务与经济.1994(4):68-72
22 马文祥.动态规划与证券交易.农金纵横.1996(3):60-61
23 叶松年.动态规划在经营决策中的应用.水利电力机械.1995(3):2-5,25
24 潘珩.动态规划方法在企业生产物流控制中的应用研究.物流技术.2004(4):77-78
25 陈守煜,马建琴,邱林.多维多目标模糊优选动态规划及其在农业灌溉中的应用.水利学报.2002(4):35-40
26 崔振才,郭林华,田文苓.水资源系统模糊优化多维动态规划模型与应用.水科学进展.2000(2):75-82
27 吴鼎贤.应用动态规划安排施工计划.建筑技术.1996(12):844-845
28 徐绪松.工序问题的动态规划算法.武汉大学学报(理学版).1994(5):22-27
29 唐立新,孙德刚.单一品种项目的生产批量问题的动态规划算法.东北大学学报(自然科学版).1999(4):35-37
30 李敬祥.动态规划法进行结构优化设计.海河水利.1995(5):40-42
31 李苏北.一类最优指派问题的动态规划解法.运筹与管理.2000(1):71-75
32 刘扬.用动态规划法进行泵-管系统最优化设计.国外油田工程.1994(1):47-51
33 潘鲁萍.用动态规划方法求解最优设站问题.交通与计算机.2002(3):19-21
34 秦裕瑗.优化路问题的代数方法--论动态规划(Ⅱ).应用数学.1994(4):42-48
35 郑阳明,贾全昌.动态规划在农业土地利用结构优化中的应用.河北师范大学学报(自然科学版).1995(3):21-24
36 谢志华,郑应平.基于动态规划的学习方法.系统工程理论方法应用.1995(3):1-8
37 谭德庆.“静态”规划问题的动态规划解法.青岛大学师范学院学报.1998(2):5-6
38 翁耀明.动态规划方法在矩阵连乘积中的应用.大学数学.1997(2):125-126
39 翁耀明,汤明华.利用动态规划证明某些不等式.工科数学.1994(3):79-81
40 田园,冯珊.基于动态规划的多目标跟踪算法及实现.信息与控制.1997(1):18-22
41 V.Chvatal,D.A.Klarner and D.E.knuth.Selected combinatorial research problems.Technical Report STAN-CS-72-292,Computer Science Department,Stanford University,1972
42 William J.Masek and Michael S.Paterson.A faster algorithm computing string edit distances.Journal of Computer and System Sciences,20(1):18-31,1980
43 T.G.Szymanski.A special case of the maximal common subsequence problem.Technical Report TR-170,Comuter Science Laboratory,Princeton University,1975
44 丁万刚.随机动态规划及其应用.太原理工大学学报.2004(2):124-127,131
45 何奇.基于Pipeline的一类动态规划并行算法.计算机学报.1994(7):527-535
46 胡祥培,钱国明,胡运权.离散型动态规划模型的知识表示及其IBFS算法研究.哈尔滨工业大学学报.1996(3):119-126
47 黄勇,曲长文,苏峰,周鲁苹.基于Matlab的动态规划顺序算法的实现.烟台师范学院学报(自然科学版).2004(4):33-35,46
48 孙晚华.关于动态规划顺序求解法的教学探讨.北京交通大学学报(社科版).2004(1):65-67
49 康一梅,吴沧浦.多目标动态规划时段轮换并行算法.自动化学报.1994(5):561-568
50 罗党,刘思峰.灰色动态规划研究.系统工程理论与实践.2004(4):57-63
51 王俊,张光宇.多约束动态规划问题求解方法的探讨.经济师.2001(9):82-83
52 王兴菊,赵然杭.马尔可夫动态规划及其应用研究.西北水电.2002(1):14-18
53 问德溥.线性动态规划改进模型及其应用.水科学进展.1998(2):31-40
54 熊德琪,殷佩海.多阶段系统多目标优化的模糊优选动态规划方法及应用.中国工程科学.2000(9):67-71
55 张琳.资源分配的多目标模糊优选动态规划分析法.运筹与管理.2000(4):22-28
56 孙晓君.基于MATLAB的动态规划逆序算法的实现.纺织高校基础科学学报.2002(1):40-43
57 徐付霞.大型动态规划的分解算法.唐山师范学院学报.1998(5):8-11
58 俞嘉第,陈继先,曾新云.动态规划的单增量搜索算法.运筹与管理.1995(1):5-11
59 纪昌明,段国圣,冯尚友.多目标动态规划分层解法与Pareto最优解.系统工程理论与实践.1995(6):76-80
60 董洪波.黑龙江.谈动态规划原理的应用.水利天地.1994(4):19
61 胡海清.科学家谈《动态规划》.中国图书评论.1994(3):86-88
62 廖慧芬,邵小兵.动态规划算法的原理及应用.中国科技信息.2005(21):47
63 祁文青.动态规划.黄石高等专科学校学报.2002(4):28-32
64 储锦林.谈动态规划阶段状态的确定问题.安徽教育学院学报.2003(3):15-18
65 陈秀金.多重阶段的最佳决策--动态规划.鹭江职业大学学报.1994(2):60-71
66 丁成纲,丁尚文.动态规划中的最优性原理及方法的进一步研究.工科数学.1997(4):42-45
67 秦裕瑗.Bellman最优性原理--论动态规划(Ⅰ).应用数学.1994(3):97-102
68 倪清泉,叶恩禧.动态规划方法简介.中华劳动卫生职业病杂志.1996(1):66
69 裴廷睿.动态规划中的整体性原则与方法.湘潭大学社会科学学报.1997(4):98-100
70 曹文.全国青少年信息学奥林匹克联赛培训教材(中学高级本).第1版.南京:南京大 学出版社,2004
71 吴耀斌,曹利国,向期中.信息学奥林匹克教程.第1版.湖南:湖南师范大学出版社,2001
72 谢水英.例谈几种常见的动态规划模型.中小学电脑报NOI专刊.2007(8):15-18
73 鞠向忠,沙聚桢.一般动态规划模型及其理论初探.黑龙江科技学院学报.1994(2):59-64
74 邓成梁.动态规划方法中应注意的两个问题.运筹与管理.1996(2):46-52
75 同小军,陈绵云.动态规划中函数值序迭代法.佛山科学技术学院学报(自然科学版).2002(1):15-18
76 章新华.一种特征选择的动态规划方法.自动化学报.1998(5):101-106
77 朱江,李德生.动态规划中一类泛函方程解的存在性和逼近技巧.兰州大学学报(自然科学版).1996(4):24-27
78 Gilles Brassard等著,邱仲潘等译.算法基础.第1版.北京:清华大学出版社,2005
79 冯小虎.动态规划思想在算法设计中的应用.安徽电子信息职业技术学院学报.2004(2):72-74
80 金孚安.一类动态规划问题的解法与算法.微机发展.2001(5):29-30
81 王刚.动态规划的应用实例.云南财贸学院学报(经济管理版).2001(1):190-191
82 M.H.Alsuwaiyel著,吴伟昶等译.算法设计技巧与分析.第1版.北京:电子工业出版社,2004
83 Udi Manber著,黄林鹏等译.算法引论--一种创造性方法.第1版.北京:电子工业出版社,2005
84 王孝东.用动态规划来解背包问题.中小学电脑报NOI专刊.2007(1):33-34
85 钱杰军.例谈动态规划在竞赛中的应用.中小学电脑报NOI专刊.2007(5):26-28
86 叶清,蔡广友,郭正东.动态规划的改进算法.青岛大学学报(自然科学版).2003(4):95-99
87 江涛,王颖寒,骆静辰.信息学奥林匹克竞赛题解精编.第1版.南京:南京大学出版社,2000
88 王晓东.算法设计与分析.第1版.北京:清华大学出版社,2003
89 E.N.Gilbert and E.F.Moore.Variable-length binary encodings.Bell System Technical Journal,38(4):933-967,1959
90 Alfred V.Aho,John E.Hopcroft,and Jeffrey D.Ullman.The Design and Analysis of Computer Algorithms.Addison-Wesley,1974
91 Donald E.Knuth.Optimum binary search trees.Acta Informatica,1:14-25,1971
92 T.C.Hu and A.C.Tucker.Optimal computer search trees and variable-length alphabetic codes.SIAM Journal on Applied Mathematics,21(4):514-532,1971
93 Donald E.Knuth.Sorting and Searching,volume 3 of The Art of Computer Programming. Addison-Wesley, 1973
94 T.C.Hu and M.T.shing.Computation of matrix chain products.Part I.SIAM Journal on Computing,11(2):362-373,1982
95 T.C.Hu and M.T.shing.Computation of matrix chain products.Part II.SIAM Journal on Computing,13(2):228-251,1984
2 顾永清.试论城市的动态规划.城市规划汇刊.1994(1):40-43,65
3 常淑芬.动态规划及其在管理中的应用.华南金融研究.1997(2):71-75
4 赵奕,赵增墀,张隆昌,袁驰.动态规划在企业生产管理中的应用.纺织器材.1997(5):46-50
5 左志坚.动态规划在管理会计中的应用.西北大学学报(哲学社会科学版).1994(2):27-33
6 吴爱华,陶东兵,李承军.基于随机动态规划方法的水电站水库优化调度的研究与应用.广东水利水电.2003(1):27-29,32
7 吴爱华,周建中,陶东兵,李承军.水库优化调度中随机动态规划方法的研究与应用.计算机仿真.2003(10):41-44
8 侯增广,吴沧浦.一种基于动态规划策略的离散动态大系统递阶优化神经网络.自动化学报.1999(1):48-54
9 胡铁松,郭元裕.多目标动态规划的神经网络方法.电子学报.1999(10):71-73
10 黄西士,吴沧浦.精确求解-类动态规划问题的神经网络.控制与决策.1996(2):261-265,271
11 王彦保.离散系统最优控制中动态规划的神经网络算法.内蒙古科技与经济.2003(9):63-64
12 叶仲泉,张邦礼,曹长修.多层前馈神经网络的动态规划算法.重庆大学学报(自然科学版).1996(6):39-43
13 殷春霞,胡铁松,郭元裕.基于人工神经网络的多目标动态规划.武汉水利电力大学学报.1999(6):2-6
14 Thomas H.Cormen等著,潘金贵等译.算法导论.第1版.北京:机械工业出版社,2006
15 杜彦娟.利用动态规划数学模型求最短路径.煤炭技术.2005(1):97-98
16 施益昌,郑贤斌,李自力.基于MATLAB动态规划中最短路线的实现程序.电脑学习.2003(6):38-39
17 金锡万.库存决策中的动态规划法及其应用探索.华东冶金学院学报.1997(1):37-42
18 高雷阜.资源分配的多目标优化动态规划模型.辽宁工程技术大学学报(自然科学版).2001(5):122-124
19 卢志文.基于动态规划的资源分配算法.福建电脑.2005(2):77,74
20 宿洁,刘家壮.多阶段资产投资的动态规划决策模型.中国管理科学.2001(3):56- 62
21 张平.动态规划法在投资分配决策中的应用.税务与经济.1994(4):68-72
22 马文祥.动态规划与证券交易.农金纵横.1996(3):60-61
23 叶松年.动态规划在经营决策中的应用.水利电力机械.1995(3):2-5,25
24 潘珩.动态规划方法在企业生产物流控制中的应用研究.物流技术.2004(4):77-78
25 陈守煜,马建琴,邱林.多维多目标模糊优选动态规划及其在农业灌溉中的应用.水利学报.2002(4):35-40
26 崔振才,郭林华,田文苓.水资源系统模糊优化多维动态规划模型与应用.水科学进展.2000(2):75-82
27 吴鼎贤.应用动态规划安排施工计划.建筑技术.1996(12):844-845
28 徐绪松.工序问题的动态规划算法.武汉大学学报(理学版).1994(5):22-27
29 唐立新,孙德刚.单一品种项目的生产批量问题的动态规划算法.东北大学学报(自然科学版).1999(4):35-37
30 李敬祥.动态规划法进行结构优化设计.海河水利.1995(5):40-42
31 李苏北.一类最优指派问题的动态规划解法.运筹与管理.2000(1):71-75
32 刘扬.用动态规划法进行泵-管系统最优化设计.国外油田工程.1994(1):47-51
33 潘鲁萍.用动态规划方法求解最优设站问题.交通与计算机.2002(3):19-21
34 秦裕瑗.优化路问题的代数方法--论动态规划(Ⅱ).应用数学.1994(4):42-48
35 郑阳明,贾全昌.动态规划在农业土地利用结构优化中的应用.河北师范大学学报(自然科学版).1995(3):21-24
36 谢志华,郑应平.基于动态规划的学习方法.系统工程理论方法应用.1995(3):1-8
37 谭德庆.“静态”规划问题的动态规划解法.青岛大学师范学院学报.1998(2):5-6
38 翁耀明.动态规划方法在矩阵连乘积中的应用.大学数学.1997(2):125-126
39 翁耀明,汤明华.利用动态规划证明某些不等式.工科数学.1994(3):79-81
40 田园,冯珊.基于动态规划的多目标跟踪算法及实现.信息与控制.1997(1):18-22
41 V.Chvatal,D.A.Klarner and D.E.knuth.Selected combinatorial research problems.Technical Report STAN-CS-72-292,Computer Science Department,Stanford University,1972
42 William J.Masek and Michael S.Paterson.A faster algorithm computing string edit distances.Journal of Computer and System Sciences,20(1):18-31,1980
43 T.G.Szymanski.A special case of the maximal common subsequence problem.Technical Report TR-170,Comuter Science Laboratory,Princeton University,1975
44 丁万刚.随机动态规划及其应用.太原理工大学学报.2004(2):124-127,131
45 何奇.基于Pipeline的一类动态规划并行算法.计算机学报.1994(7):527-535
46 胡祥培,钱国明,胡运权.离散型动态规划模型的知识表示及其IBFS算法研究.哈尔滨工业大学学报.1996(3):119-126
47 黄勇,曲长文,苏峰,周鲁苹.基于Matlab的动态规划顺序算法的实现.烟台师范学院学报(自然科学版).2004(4):33-35,46
48 孙晚华.关于动态规划顺序求解法的教学探讨.北京交通大学学报(社科版).2004(1):65-67
49 康一梅,吴沧浦.多目标动态规划时段轮换并行算法.自动化学报.1994(5):561-568
50 罗党,刘思峰.灰色动态规划研究.系统工程理论与实践.2004(4):57-63
51 王俊,张光宇.多约束动态规划问题求解方法的探讨.经济师.2001(9):82-83
52 王兴菊,赵然杭.马尔可夫动态规划及其应用研究.西北水电.2002(1):14-18
53 问德溥.线性动态规划改进模型及其应用.水科学进展.1998(2):31-40
54 熊德琪,殷佩海.多阶段系统多目标优化的模糊优选动态规划方法及应用.中国工程科学.2000(9):67-71
55 张琳.资源分配的多目标模糊优选动态规划分析法.运筹与管理.2000(4):22-28
56 孙晓君.基于MATLAB的动态规划逆序算法的实现.纺织高校基础科学学报.2002(1):40-43
57 徐付霞.大型动态规划的分解算法.唐山师范学院学报.1998(5):8-11
58 俞嘉第,陈继先,曾新云.动态规划的单增量搜索算法.运筹与管理.1995(1):5-11
59 纪昌明,段国圣,冯尚友.多目标动态规划分层解法与Pareto最优解.系统工程理论与实践.1995(6):76-80
60 董洪波.黑龙江.谈动态规划原理的应用.水利天地.1994(4):19
61 胡海清.科学家谈《动态规划》.中国图书评论.1994(3):86-88
62 廖慧芬,邵小兵.动态规划算法的原理及应用.中国科技信息.2005(21):47
63 祁文青.动态规划.黄石高等专科学校学报.2002(4):28-32
64 储锦林.谈动态规划阶段状态的确定问题.安徽教育学院学报.2003(3):15-18
65 陈秀金.多重阶段的最佳决策--动态规划.鹭江职业大学学报.1994(2):60-71
66 丁成纲,丁尚文.动态规划中的最优性原理及方法的进一步研究.工科数学.1997(4):42-45
67 秦裕瑗.Bellman最优性原理--论动态规划(Ⅰ).应用数学.1994(3):97-102
68 倪清泉,叶恩禧.动态规划方法简介.中华劳动卫生职业病杂志.1996(1):66
69 裴廷睿.动态规划中的整体性原则与方法.湘潭大学社会科学学报.1997(4):98-100
70 曹文.全国青少年信息学奥林匹克联赛培训教材(中学高级本).第1版.南京:南京大 学出版社,2004
71 吴耀斌,曹利国,向期中.信息学奥林匹克教程.第1版.湖南:湖南师范大学出版社,2001
72 谢水英.例谈几种常见的动态规划模型.中小学电脑报NOI专刊.2007(8):15-18
73 鞠向忠,沙聚桢.一般动态规划模型及其理论初探.黑龙江科技学院学报.1994(2):59-64
74 邓成梁.动态规划方法中应注意的两个问题.运筹与管理.1996(2):46-52
75 同小军,陈绵云.动态规划中函数值序迭代法.佛山科学技术学院学报(自然科学版).2002(1):15-18
76 章新华.一种特征选择的动态规划方法.自动化学报.1998(5):101-106
77 朱江,李德生.动态规划中一类泛函方程解的存在性和逼近技巧.兰州大学学报(自然科学版).1996(4):24-27
78 Gilles Brassard等著,邱仲潘等译.算法基础.第1版.北京:清华大学出版社,2005
79 冯小虎.动态规划思想在算法设计中的应用.安徽电子信息职业技术学院学报.2004(2):72-74
80 金孚安.一类动态规划问题的解法与算法.微机发展.2001(5):29-30
81 王刚.动态规划的应用实例.云南财贸学院学报(经济管理版).2001(1):190-191
82 M.H.Alsuwaiyel著,吴伟昶等译.算法设计技巧与分析.第1版.北京:电子工业出版社,2004
83 Udi Manber著,黄林鹏等译.算法引论--一种创造性方法.第1版.北京:电子工业出版社,2005
84 王孝东.用动态规划来解背包问题.中小学电脑报NOI专刊.2007(1):33-34
85 钱杰军.例谈动态规划在竞赛中的应用.中小学电脑报NOI专刊.2007(5):26-28
86 叶清,蔡广友,郭正东.动态规划的改进算法.青岛大学学报(自然科学版).2003(4):95-99
87 江涛,王颖寒,骆静辰.信息学奥林匹克竞赛题解精编.第1版.南京:南京大学出版社,2000
88 王晓东.算法设计与分析.第1版.北京:清华大学出版社,2003
89 E.N.Gilbert and E.F.Moore.Variable-length binary encodings.Bell System Technical Journal,38(4):933-967,1959
90 Alfred V.Aho,John E.Hopcroft,and Jeffrey D.Ullman.The Design and Analysis of Computer Algorithms.Addison-Wesley,1974
91 Donald E.Knuth.Optimum binary search trees.Acta Informatica,1:14-25,1971
92 T.C.Hu and A.C.Tucker.Optimal computer search trees and variable-length alphabetic codes.SIAM Journal on Applied Mathematics,21(4):514-532,1971
93 Donald E.Knuth.Sorting and Searching,volume 3 of The Art of Computer Programming. Addison-Wesley, 1973
94 T.C.Hu and M.T.shing.Computation of matrix chain products.Part I.SIAM Journal on Computing,11(2):362-373,1982
95 T.C.Hu and M.T.shing.Computation of matrix chain products.Part II.SIAM Journal on Computing,13(2):228-251,1984