文档介绍：动态规划是信息学竞赛中选手必须熟练掌握的一种算法, 他以其多元性广受出题者的喜爱. 动态规划首次进入信息学奥赛是在 IOI94 (数字三角形) ,在国内首次出现是在 NOI95 。此后动态规划成为信息学奥赛的必考算法之一。[ 编辑本段] 概念及意义动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process) 最优化的数学方法。 20 世纪 50 年代初美国数学家 等人在研究多阶段决策过程(multistep decision process) 的优化问题时,提出了著名的最优化原理(principle of optimality) ,把多阶段过程转化为一系列单阶段问题, 利用各阶段之间的关系, 逐个求解, 创立了解决这类过程优化问题的新方法——动态规划。 1957 年出版了他的名著 Dynamic Programming ,这是该领域的第一本著作。动态规划问世以来, 在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题, 用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划( 如线性规划、非线性规划), 只要人为地引进时间因素, 把它视为多阶段决策过程, 也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样, 具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题, 由于各种问题的性质不同, 确定最优解的条件也互不相同, 因而动态规划的设计方法对不同的问题, 有各具特色的解题方法, 而不存在一种万能的动态规划算法, 可以解决各类最优化问题。因此读者在学****时, 除了要对基本概念和方法正确理解外, 必须具体问题具体分析处理, 以丰富的想象力去建立模型, 用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。[ 编辑本段] 基本模型多阶段决策过程的最优化问题。在现实生活中, 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都需要作出决策, 从而使整个过程达到最好的活动效果。当然, 各个阶段决策的选取不是任意确定的, 它依赖于当前面临的状态, 又影响以后的发展, 当各个阶段决策确定后, 就组成一个决策序列, 因而也就确定了整个过程的一条活动路线,如图所示: (看词条图) 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就称为多阶段决策问题。[ 编辑本段] 记忆化搜索给你一个数字三角形, 形式如下: 123456789 10 找出从第一层到最后一层的一条路, 使得所经过的权值之和最小或者最大. 无论对与新手还是老手,这都是再熟悉不过的题了,很容易地, 我们写出状态转移方程: f(i, j)=a[i, j]+ min{f(i+1, j), f(i+1, j+ 1)} 对于动态规划算法解决这个问题, 我们根据状态转移方程和状态转移方向, 比较容易地写出动态规划的循环表示方法。但是, 当状态和转移非常复杂的时候, 也许写出循环式的动态规划就不是那么简单了。解决方法: 我们尝试从正面的思路去分析问题, 如上例, 不难得出一个非常简单的递归过程: f1:=f(i-1,j+1); f2:=f(i-1,j); if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j]; 显而易见, 这个算法就是最简单的搜索算法。时间复杂度为 2n, 明显是会超时的。分析一下搜索的过程, 实际上, 很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次。为了避免浪费, 很显然,我们存放一个 opt 数组: Opt[i, j]- 每产生一个 f(i, j), 将 f(i, j) 的值放入 opt 中,以后再次调用到 f(i, j) 的时候,直接从 opt[i, j] 来取就可以了。于是动态规划的状态转移方程被直观地表示出来了, 这样节省了思维的难度, 减少了编程的技巧, 而运行时间只是相差常数的复杂度,避免了动态规划状态转移先后的问题,而且在相当多的情况下, 递归算法能更好地避免浪费, 在比赛中是非常实用的.[ 编辑本段] 状态决策决策: 当前状态通过决策, 回到了以前状态. 可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。状态: 我们一般在动规的时候所用到的一些数组, 也就是用来