刘雄辉　汪红宇　陈义明

摘要：动态规划算法是运筹学的一个分支，是求解多阶段决策最优的方法。该文介绍了使用动态规划算法的一定条件，并详写了使用动态规划算法解决决策性问题时的三大阶段和三大要素，以及动态规划算法与分治算法、贪心算法的关系。并以动态规划算法在ACM算法竞赛中的应用，来加强对于动态规划的理解。

关键词：动态规划；最优；算法；策略

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）18-0238-02

动态规划算法是求解多阶段决策最优的方法，它与分治算法和贪婪算法有一定的相似度，它能够高效地处理分治和贪婪不可以处理的问题。

1使用动态规划算法的条件

动态规划算法从问世到现在，在很多方面得到了广泛运用。如最短路线、背包问题、最小生成树等问题，动态规划算法比用其他算法求解更加便利。然而动态规划并不适用于所有的问题，只有满足以下条件才能使用动态规划求解：

1）最优化原理

2）无后效性

最优化原理是动态规划的基础，假使一个问题没有最优化原理的支持，就不能使用动态规划算法求解。那么最优化原理是什么呢？简单来说就是一个最优策略的子策略，对于它的初态和终态而言也必是最优的。

例如图1，状态1→状态7的最优策略为A1-A2-A3-A6-A7，那么其子策略A2-A3也一定是状态2→状态6的最优策略。

无后效性是问题可使用动态规划算法的一个标记。我们可以理解为：一个阶段的状态只要确定了，那么后面过程的演化不会受前面状态和策略影响，以图1举例说明：状态3和状态4只能够由状态2经过决策A2、A4得来，和其他的状态没有任何的关系。……