算法合集之动态规划的深入探讨.doc

把握本质，灵活运用——动态规划的深入探讨
把握本质，灵活运用——动态规划的深入探讨
-- IOI’99中国集训队优秀论文选
IOI’99中国集训队优秀论文选 --
IOI’99中国集训队优秀论文选 --
把握本质，灵活运用——动态规划的深入探讨
浙江省萧山中学来煜坤

【关键字】动态规划构思实现
【摘要】本文讨论了动态规划这一思想的核心内容和其基本特点，探讨了动态规划思想的适用范围，动态规划子问题空间和递推关系式确立的一般思路。通过例子说明在子问题确立过程中的一些问题的解决办法：通过加强命题或适当调节确定状态的变量等手段帮助建立动态规划方程，通过预处理使动态规划的过程容易实现等。接着，分析动态规划实现中可能出现的空间溢出问题及一些解决办法。总结指出，动态规划这一思想，关键还在于对不同的问题建立有效的数学模型，在把握本质的基础上灵活运用

一、引言
动态规划是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态规划思想来解决的问题，使用动态规划是比较明智的选择。
能够用动态规划解决的问题，往往是最优化问题，且问题的最优解(或特定解)的局部往往是局部问题在相应条件下的最优解，而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系。如果这种关系难以建立，即问题的特定解不仅依赖于子问题的特定解，而且与子问题的一般解相关，那么，一方面难以记录下那么多的“一般解”，另一方面，递推的效率也将是很低的；此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享相同的子问题。(如果子问题不重叠，则宜使用其它方法，如分治法等。)
动态规划一般可以通过两种手段比较高效地实现，其一是通过自顶向下记忆化的方法，即通过递归或不递归的手段，将对问题最优解的求解，归结为求其子问题的最优解，并将计算过的结果记录下来，从而实现结果的共享；另一种手段，也就是最主要的手段，通过自底向上的递推的方式，由于这种方式代价要比前一种方式小，因而被普遍采用，下面的讨论均采用这种方式实现。动态规划之所以具有高时效，是因为它在将问题规模不断减小的同时，有效地把解记录下来，从而避免了反复解同一个子问题的现象，因而只要运用得当，较之搜索而言，效率就会有很大的提高。
动态规划的思想，为我们解决与重叠子问题相关的最优化问题提供了一个思考方向：通过迭代考虑子问题，将问题规模减小而最终解决问题。适于用动态规划解决的问题，是十分广泛的。动态规划的思想本身是重要的，但更重要的是面对具体问题的具体分析。要分析问题是否具备使用动态规划的条件，确定使用动态规划解题的子问题空间和递推关系式等，以及在(常规)内存有限的计算机上实现这些算法。下面分别就构思和实现两个方面进一步探讨动态规划这一思想。

二、动态规划解题的构思
当我们面对一个问题考虑用动态规划时，十分重要的一点就是判断这个问题能否用动态规划高效地解决。用动态规划构思算法时，往往要考虑到这个问题所涉及到的子问题(子问题空间)，以及如何建立递推式，并最终实现算法。其实，这些过程往往是交织在一起的，子问题空间与递推关系本身就是紧密相联的，为了有效地建立起递推关系，有时就要调整子问题空间；而根据大致确定的子问题空间又可以启发我们建立递推关系式。而能否最终用一个递推关系式来联系问题与其子问题又成了判断一个问题能否使用动态规划思想解决的主要依据。因而孤立地来看这其中的每一部分，硬把思考过程人为地分成几个部分，是困难的，也是不必要的。而且动态规划这种思想方法，没有固定的数学模型，要因题而异，因而也就不可能归纳出一种“万能”的方法。但是对大多数问题而言，还是能够有一个基本的思考方向的。

首先，要大致分析一个问题是否可能用动态规划解决。如果一个问题难以确定子问题，或问题与其子问题的特殊解之间毫无关系，就要考虑使用其它方法来解决(如搜索或其它方法等)。做一个大概的判断是有必要的，可以防止在这上面白花时间。通常一个可以有效使用动态规划解决的问题基本上满足以下几方面的特性：
子问题的最优解仅与起点和终点(或有相应代表意义的量)有关而与到达起点、终点的路径无关。
大量子问题是重叠的，否则难以体现动态规划的优越性。

下面以IOI’97的“字符识别”问题为例进行分析一般情况下动态规划思路的建立。
IOI’97的字符识别问题，题目大意是：在FONT.DAT中是对(空格)、A—Z这27个符号的字形说明。对每一个符号的字符点阵，用20行每行20个“0”或者“1”表示。在另一个输入文件中，描述了一串字符的点阵图象(共N行)，但字符可能是“破损的”，即有些0变成了1，而有些1变成了0。每行固定也为20个“0”或“1”，但