信息学竞赛中动态规划类程序设计题型讨论及分析方法初探.doc

信息学竞赛中动态规划类程序设计算法分析及解题方法初探四川省内江市第六中学 廖林春内容摘要：动态规划类程序设计题型历来是信息学竞赛考察的重点，也是难点，它要求选手具备较强的数学分析功底和严密的逻辑分析能力本文详细探讨了在高中阶段信息学竞赛中动态规划类程序设计的算法分析方法、解题思路和程序实现方法，并提出了笔者在实际解题分析与培养学生过程中总结的此类算法分析方法及分析观点关键词：算法、动态规划、动态转移方程、最优值、最优解、最优子结构高中阶段信息学竞赛在文中特指信息学奥林匹克全国青少年联赛(NOIP)及其以上赛事(NOI、IOI)，其考察内容广泛，主要算法分析方法涵盖了分治策略、贫心策略、动态规划、回溯与分枝限界、网络流等等其中动态规划类题型自IOI94引入此项赛事以来，逐步成为了考察的重点当然不是因为此类题目原型繁多，而是其要求竞赛选手需具备较强的数学分析功底和严密的逻辑分析能力，可考查性强一、什么是动态规划？动态规划类题目具备怎样的特征呢？首先，动态规划是运筹学的一个分支，是求解决策过程最优化问题的数学分析方法它将多阶段过程转化为一系列单阶段问题，并严格分阶段求解每阶段的最优值，最终导出多阶段问题的最优解。

理解动态规划的概念需要强调：在每个单阶段分析过程中，并非仅得到一个最优值，而可能是多个的最优值，是为分析后继阶段垫定了子问题解的基础这也是算法分析中贫心算法与动态规划算法分析的最本质的差异其次，动态规划是相对于递归算法的算法分析方法递归算法以其简明、概括的分析向我们揭示了一种“由上而下”问题解决方法其缺点在于：递归至问题较底层时，容易受到大量重叠子问题的影响，使得运算重复、效率较低如果我们采用“备忘录”的方式记录子问题的解来克服这些缺陷，就发展出了完备的“由上而下”的问题解决方法——递归备忘录法动态规划正是相对于“由上而下”而提出的“自下而上”问题解决方法在问题求解过程中主动求解并记录子问题的解，使得大量的重叠子问题运算减少至一次运算即可，最终“自下而上”推导出问题的最优解解综上所述，动态规划类题目必将具备如下特征：1、 问题必须具备最优子结构因为问题的最优解是建立在一系列相关子问题的最优值的基础之上，这就要求这些子问题必须与问题本身具备完全相同的解结构、相同的分析方法，也就是原问题与子问题属同一问题，仅是规模不同，也使得求解问题的程序代码具备复用性2、 可能存在大量的重叠子问题减少重叠子问题的运算次数是动态规划算法的重要设计目标，也是提高代码效率重要途径。

根据问题的实际意义，必须强调有效的重叠子问题，因为动态规划算法在运算子问题时，本身不如“递归备忘录法”具有明确的目的性，有关后继子问题运算会用到哪些先行运算的子问题的猜想是盲目的，也就有可能花了大量的时间运算了大量的无关的子问题，这也是程序设计中在“动态规划算法”与“递归备忘录法”之间选择的重要指标3、 问题本身一定是多阶段的决策问题这要求问题的求解过程可以分成若干个阶段，每个阶段可包含一个或多少最优值状态阶段不仅揭示了子问题求解的先后关系，而且也揭示程序设计中的处理流程4、 问题各阶段的划分符合无后效性原则此原则揭示了动态规划适用的范围是解决当前阶段决策与过去状态无关的问题简单的说就是：过去的步骤只能通过当前状态影响未来的发展，当前状态是对历史的总结或者说过去的状态仅能直接作用于后一阶段的决策，而不能跨越式的直接影响其他后继阶段的决策，换言之就是影响必须是层层传递的二、动态规划类问题的算法分析方法讨论解决动态规划类问题的关键在于求解问题的动态转换方程对于如何求取动态转换方程，大多数的书籍中都没有具体、详实的介绍，取而代之的是经验的总结与推广，也常常是围绕题目本身介绍具体方法，缺乏普遍的指导意义。

根据笔者多年的学习与经验总结，在上述基础之上，提出较为完善的算法分析与程序设计方法，供参考与讨论在讨论展开前，请仔细阅读我们将反复分析的示例：最长公共子序列问题一个给定序列的子序列是在该序列中删去若干元素后得到的序列，子序列元素下标保持严格递增这样给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列例如：若X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}，则序列{B,C,A}是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列最长公共子序列问题是：给定两个序列X={X1,X2,…,Xm}和Y={Y1,Y2,…,Yn}，找出X和Y的最长公共子序列围绕上述问题，我们将从以下几方面展开分析与设计实现：1、 审查题意，判定题型审题是决定后期分析方法的指导，是具体程序设计的基础审题分为两个层次：初审、细审初审阶段读懂题目大意，初步判断题目在算法分析中的大致类型细审阶段理解问题题意，明确问题求解目标，特别是分析出问题解结构的特征与构成，为后继问题本身的描述、最优解的构造垫定基础针对上述题目，结合动态规划类题目必备特征，可以初步判定上述问题属于动态规划类问题。

对于问题解结构，可以采用向量描述形式{Z1，Z2，…，Zk}(k<=m,k<=n)若采用记录向量的形式来记录程序中的可能解向量，规模将异常庞大，因此宜采用记录所有子问题的最优值的方法，最终构造求解原问题的最优解对于读者疑惑的：什么是子问题的最优值、如何构造问题的最优解等问题，将放在解决好问题的描述后再介绍2、 用有意义的数学函数形式刻画并描述问题及其子问题动态规划的子问题是规模小于问题本身的同类问题，因此它们具有完全相同的解结构特征与求解思路，也就可以采用相同的描述形式能否完成用数学函数形式刻画并描述问题的关键在于如何判定描述问题的规模数学函数往往采用参数的具体值来描述一个具体的问题所以我们也可以设计一个通用的函数式来描述问题本身，而采用不同的参数值来具体描述问题以及不同的子问题比如：F(X1,X2,…,Xn)，表示由n个参变量决定的某问题，当参变量取具体值时即是一个具体问题，当参变量值不同时代表不同规模相同类型的一个具体问题接下来要解决F(X1,X2,…,Xn)有意义的问题，也就是F(X1,X2,…,Xn)代表什么？如果F(X1,X2,…,Xn)代表这个子问题的最优解，经分析这个最优解可以采用向量描述，那么问题在存储上将变的异常复杂。

因此F(X1,X2,…,Xn)可以赋予其一个与最优解相关的意义，当然最终可以通过这一系列的意义解释导出问题的最优解，我们称其为最优值具体分析上述题目：问题与X和Y序列，X、Y可以用字符串形式描述，那么要描述这个问题实际上可以采用X、Y序列的下标做为规模的参变题，从而描述问题及相关的子问题如：F(x,y)，其中x代表X序列或子序列的下标规模，y代表Y序列或子序列的下标规模具体的F(2,5)表示X序列取前2个元素的子序列，Y序列取前5个元素的子序列的一个子问题；F(X.length,Y.length)代表原问题对于F(x,y)可以解释为这样的有意义的量：在X序列的前x个元素的子序列、Y序列的前y个元素的子序列中有F(x,y)个元素是相同的3、 依据题目函数描述中的参变量，确定描述所有相关子问题的动规表动规表其实是为动态转移方程提供状态记录与转移的区域什么是状态呢？其实就是一个子问题及其最优值每个子问题在这个表中都有一项记录且记录其最优值我们将题目函数描述的参变量视为这个动规表的维下标，也就说具有一个参变量的以一维数组描述之，不同的元素正好对应的下标描述的参变量的规模代表的子问题及其最优值，类推具有两个参变量问题正好对应二维数组做为动规表。

上述问题可采用二维数组做动规表，F(x,y)在表中对应的元素，代表了在规模参数x(比如：横坐标)、y(比如：纵坐标)规定的子问题，其值是这个子问题的最有值，这样有关这个问题的所有子问题均被枚举在了这张表中4、 依据动规表确定问题的动态转移方程在动规表中，每个元素代表一个子问题，这样就非常容易判定当前问题是由哪些子问题转移而来(具体的分析结论)，并相应得到问题的动态转移方程(通用的分析结论)经验表明将动规表作在纸上，可以快速的分析出问题的动态转换方程上述问题动规表分析(如左图)：X6=Y4时F(6,4)由F(5,3)+1转移而来X6<>Y4时，为保持最长序列值则F(6,4)由Max(F(6,2)，F(5,4))+1转移而来这样简化、清晰的分析过程进一步分析得到问题的转移方程为(如下图)：5、根据动态转移方程确定的子问题求解顺序，确定问题阶段具体划分在前面已经介绍过问题的阶段划分不仅揭示了子问题求解的先后关系，而且也揭示程序设计中的处理流程，也就预示了动规表的填充过程对于这些分析，在熟练的情况下可很容易直接得出的，如果不够熟练，方法就是对照上述动规分析表，一定要在当前问题求解前求解出所以前驱子问题的最优值。

针对此题的阶段划分可以采用F(x,y)中每个确实的x下标的子序列，与Y序列所有子序列构成的子问题划为一个阶段(如下左图)，每个确实的y下标的子序列，与X序列所有子序列构成的子问题划为一个阶段(如下右图)，其子问题求解顺序为：6、依据阶段具体划分确定初始子问题的值初始子问题是不以其他子问题为基础，可以直接确定其值的子问题在动态规划表中体现出来就是不满足动态转移方程的哪些子问题，他们往往存在于边界之上比如：上述问题中所有的F(1,y)，F(x,1)都是初始子问题，需预先赋予初值，作为由下而上递推的基础,其初始化伪代码为：for(i=1;i

回顾自己从事高中信息学竞赛经历，发现自己一路走得并不平坦，所以特别写作了这篇论文，内容针对竞赛中最难翻越的高山——动态规划类程序设计，意在自我总结、与人交流的同时，并为相关教师、竞赛同学提供几点思路、几点启示。