动态规划法在程序设计中的应用

摘要摘 要：探讨动态规划法的本质及在计算机程序设计中的应用。提出求解Fibonacci序列的3种算法，即递归法、自底向上和自顶向下动态规划法，证明将动态规划法用于程序设计，能降低算法的时间复杂度和空间复杂度。

关键词关键词：动态规划；Fibonacci序列；程序设计；自底向上；自顶向下

中图分类号：TP302

文献标识码：A 文章编号文章编号：16727800（2014）008003203

作者简介作者简介：邓国强（1979-），男，湖北荆州人，硕士，桂林电子科技大学数学与计算科学学院讲师，研究方向为数值计算、优化算法；唐敏（1980-），女，广西桂林人，华东师范大学软件学院博士研究生，桂林电子科技大学数学与计算科学学院讲师，研究方向为算法设计与分析。

0 引言

动态规划（Dynamic Programming， DP）是求解一类复杂问题的方法，在数学、计算机科学、经济学、生物信息学等领域应用广泛。其基本思想是把原问题分解成若干子问题，这些子问题是交叠的（overlapping）并且具有最优子结构。对于给定的一个问题，需要求解原问题的不同子问题，结合子问题的解以获得整个问题的解。当使用蛮力法求解问题时，会生成很多子问题并重复求解，而动态规划对每个子问题仅求解一次，减少了计算量，一旦计算出给定子问题的解，就被存储起来以备后续使用。对于一个子问题个数随着输入规模成指数增长的问题，动态规划法特别有效。本文将动态规划法用于计算机程序设计中，给出求解Fibonacci序列的3种不同算法，并对其进行时间复杂度和空间复杂度分析。

1 动态规划法起源

动态规划法起源于1940年，Richard Bellman提出求解问题的过程需要一个接一个作出决策，特别指出在较大的决策中嵌套着较小的决策问题。随后，IEEE将该领域作为系统分析和工程上的课题。Bellman的贡献主要在于给出了Bellman方程，将优化问题描述成递归的形式，即动态规划的核心。Bellman称之为“最优性原理”，在计算机科学中，将一个问题递归的分解称为最优子结构，如果子问题能递归地嵌套进更大的问题中，在较大问题的值和子问题的值之间存在一个关系，在优化中将这种关系称为Bellman方程。

动态规划法可用于优化计算，比如求两点之间的最短路径，多个矩阵相乘的最快方法。在生物信息学中，DP可用于解决序列比对、蛋白质折叠、DNA结构预测等。动态规划法检查求解问题的所有可能路径，找出最好的解，如果问题的规模能满足DP检查到所有的解，则DP能找到最优解。而贪心法挑选当前看起来是最好的解，但不保证能得到最优解。

2 应用方式

应用动态规划法必须满足两个特性：最优子结构和交叠子问题。如果一个问题能分解成互不相交叠的子问题，可采用分治策略。这就是归并排序和快速排序并不属于动态规划问题的原因。最优子结构（Optimal substructure）指的是给定的最优问题的解能结合它的子问题的解来求解。首先需要设计动态规划的解，检查问题是否具有最优子结构，这个最优子结构可用递归形式描述。例如，给定一个图G=（V，E），求从顶点u到顶点v的最短路径p这一问题具有最优子结构。交叠子问题指子问题规模非常小，任何求解原问题的递归算法能求解相同的子问题，而不是生成新的子问题。

动态规划解决计算机程序设计问题有两种方式：

（1）自顶向下（Top-down approach）。

如果原问题能递归使用子问题的解，并且子问题是互相交叠的，那么可以将这些子问题存储起来，比如存放在一个表中，当需要求解一个新的子问题时，首先检查表中是否已经存储了这个子问题的解，如果已经存储了，直接取出使用即可，否则求解这个子问题并将这个子问题的解存入表中。

（2）自底向上（Bottom-up approach）。

如果根据子问题迭代求解出原问题，那么可以使用自底向上的方式，首先求解子问题，然后构建更大的子问题。通过使用较小子问题的解生成越来越大的子问题，直至整个问题的解。

3 Fibonacci序列求解

考虑生成Fibonacci序列的递推公式，

在算法2和算法3中，fib（2）仅计算一次，使用它计算fib（4）和fib（3），而不是每次需要用到fib（2）时都重新计算一次。

4 Fibonacci序列求解算法小结

在第3节中，分别使用了传统的递归法、自顶向下的动态规划法、自底向上的动态规划法求解Fibonacci序列的第n项。表1给出了3种算法的时间复杂度和空间复杂度。

由此可见，采用动态规划法可降低算法的时间复杂度，而在自顶向下和自底向上的动态规划法中，自底向上的方法使用的存储空间最少。

值得一提的是，对于Fibonacci序列，有一个闭形式的

解，即Binet公式，比起动态规划法求解Fibonacci序列来

说，它的效率更高，但这已经超出了程序设计的范畴。

5 结语

任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的为线性规划）模型来描述[5，6]。从原则上说，一般也可以用非线性规划方法求解。用动态规划方法的优越性主要体现在：易于确定全局最优解；能得到一族解，有利于分析结果；能利用经验，提高求解效率。动态规划法的不足之处在于：到目前为止，没有一个统一的标准模型可供应用；构造动态规划模型时，必须满足“无后效性”条件；在数值求解时，存在“维数障碍”。一些用动态规划法解决的典型问题大多数都是确定型的，而对于连续型、随机型问题解决较少。有些问题并未能完全解决，如背包问题、货郎担问题，在理论和算法上还有许多问题。通过Fibonacci序列的求解，证明将动态规划的思想用于程序设计上，可以节省存储空间，降低时间复杂度。这一方法需要进一步研究，以解决更多的问题。

参考文献参考文献：

[1] KENNETH H， ROSEN. Discrete mathematics and its applications[M].American： McGrawHill， 2012.

[2] ROBERT L， KRUSE， ALEXANDER J，et al.数据结构与程序设计——C++语言描述[M]. 北京：高等教育出版社， 2010.

[3] 张铭，王腾蛟，赵海燕.数据结构与算法[M].北京：高等教育出版社， 2008.

[4] JON KLEINBERG，EVA TARDOS.Algorithm mesign[M]. 北京：清华大学出版社， 2011.

[5] HILLIER F S，LIEBERMAN G J.Introduction to operations research[M].北京：清华大学出版社，2010.

[6] 《运筹学》教材编写组.运筹学[M].北京：清华大学出版社，2012.

责任编辑（责任编辑：陈福时）

英文标题 Dynamic Programming in Application of Computer Programming

英文摘要Abstract：The nature of dynamic programming and its application for computer programming are discussed. We present three methods for solving Fibonacci sequence， which are the recursive method， bottomup approach and topdown approach respectively. The analysis about time complexity and space complexity for three algorithms is demonstrated that if use dynamic programming in computer programming， the time and space complexity will be decreased.

英文关键词Key Words： Dynamic Programming； Fibonacci Sequence； Computer Programming； Bottomup； Topdown