动态规划初步.pdf

动态规划初步动态规划初步
动态规划简介 （Dynamic Programming）
动态规划是运筹学的一个分支。它是解决多阶段决策过程
最优化问题的一种方法。1951年，
了解决这类问题的“最优化原则”，1957年发表了他的名著《动
态规划》，该书是动态规划方面的第一本著作。动态规划问世
以来，在工农业生产、经济、军事、工程技术等许多方面都得
到了广泛的应用，取得了显著的效果。
动态规划运用于信息学竞赛是在90年代初期，它以独特的
优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必
不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛
中，都至少有一道动态规划的题目。所以，掌握好动态规划，
是非常重要的。
动态规划简介
动态规划中有很多深奥的概念，使用动态规划也有很多前提
条件，当然我们不要被理论所吓倒。学****动态规划最重要的是
“一种思想方法和解题过程”，请大家积极动脑动手，跟着我一起
分析和体会其中的方法和过程，然后再独立去思考和实践。
简单地说，动态规划是怎样来解决问题的？
它与递推、递归有着密切的联系 。
递推和动态规划递推和动态规划
递递 推推

 有些问题中，相邻两项或多项数字（或有些问题中，相邻两项或多项数字（或
状态）之间存在某种关系，可以通过前状态）之间存在某种关系，可以通过前
一项或多项按照某一规律推出其后一项一项或多项按照某一规律推出其后一项
数字（或状态），或者是通过后一项或数字（或状态），或者是通过后一项或
多项按照某一规律推出其前一项数字多项按照某一规律推出其前一项数字
（或状态）。我们可将这种规律归纳成（或状态）。我们可将这种规律归纳成
如下递推关系式：如下递推关系式：
 FFn=g(F=g(Fn-1))或者或者FFn-1=g=g＇＇(F(Fn))
递递 推推

 已知初始值已知初始值FF1 ，， 通过递推关系式通过递推关系式

FFn=g(F=g(Fn-1))求出最终结果求出最终结果 FFn的递推方式称的递推方式称
为为顺推法顺推法 ；同理，把已知最终结果为；同理，把已知最终结果为

FnFn，，通过递推关系式通过递推关系式FFn-1=g=g＇＇(F(Fn))求出求出

初始值初始值FF1的递推方式称为的递推方式称为倒推法倒推法 。。
递递 推推

 FibonacciFibonacci数列：数列：HHn == HHn-1 ++ HHn-2

 FibonacciFibonacci数列大家都非常熟悉，来源于数列大家都非常熟悉，来源于
中世纪数学家中世纪数学家 FibonacciFibonacci提出的一个问提出的一个问
题：一对刚出生的兔子过两个月后题：一对刚出生的兔子过两个月后,,可可
以繁殖一对新兔子以繁殖一对新兔子,,问原有雌雄各一只问原有雌雄各一只
兔子，经过十一个月后，能繁殖多少只兔子，经过十一个月后，能繁殖多少只
兔子。兔子。
递递 推推

【【例题例题11】】
 同一平面内有同一平面内有nn（（nn≤≤500500））条直线，已条直线，已
知其中知其中 pp（（pp≥≥22））条直线相交于同一条直线相交于同一
点，则这点，则这nn条直线最多能将平面分割成条直线最多能将平面分割