动态规划一、动态规划简介动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家贝尔曼（R.Bellman）提出了解决这类问题的“最优化原则”，1957年发表了他的名著动态规划，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。动态规划是一种方法，是考虑问题的一种途径，而不是一种算法。因此，它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。二、动态规划的几个基本概念想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指标函数。1阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量
