吕丹 杨子寒 周君

摘要：动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。文中首先分别使用递归法和动态规划法对斐波拉契数列项进行求解，通过其不同的求解过程详细说明动态规划算法的原理以及建模过程，并突出用其求解具有重叠子问题的问题的优势。最后，文中通过用其对生活中的房屋物品购买以及旅行花费最少路径选择问题进行建模，完成相应的分析求解。

关键词：动态规划；运筹学；重叠子问题；问题建模

中图分类号：TP30 文献标识码：A 文章编号：1009-3044（2018）17-0253-03

1引言

20世纪50年代初，美国数学家R.E.Bellman等人在优化多阶段决策过程的研究中，提出了著名的最优化原理。即把多阶段过程转化为一系列单阶段问题，并利用各阶段之间的关系，逐个求解，为解决这类过程优化问题创造了一种新的方法，即动态规划。使用动态规划中的最优化原则，可以将某一个活动过程划分为多个相互关联的阶段。基于前一阶段的决策结果，依次选择出各个不同阶段所处条件下可以选择的最优方案。通过这种方式，不仅可以确定当前状态到目标状态的最优值，而且还可以求出到中间状态的最优值，从而大大优化整个过程的经济效益。

由于用动态规划的思想解决问题，不仅可以令问题简化，而且可以避免计算的冗余。因此，动态规划问世后被广泛应用于生产调度，经济管理和优化控制等领域。

2动态规划算法介绍

两种解法的不同之处：