动态规划的深入探讨

我不是女神ヾ 2021-11-15 11:22 352阅读 0赞

### 一、引言 ###

动态规划是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态规划思想来解决的问题，使用动态规划是比较明智的选择。

能够用动态规划解决的问题，往往是最优化问题，且问题的最优解(或特定解)的局部往往是局部问题在相应条件下的最优解，而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系。如果这种关系难以建立，即问题的特定解不仅依赖于子问题的特定解，而且与子问题的一般解相关，那么，一方面难以记录下那么多的“一般解”，另一方面，递推的效率也将是很低的；此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享相同的子问题。(如果子问题不重叠，则宜使用其它方法，如分治法等。)

动态规划一般可以通过两种手段比较高效地实现，其一是通过自顶向下记忆化的方法，即通过递归或不递归的手段，将对问题最优解的求解，归结为求其子问题的最优解，并将计算过的结果记录下来，从而实现结果的共享；另一种手段，也就是最主要的手段，通过自底向上的递推的方式，由于这种方式代价要比前一种方式小，因而被普遍采用，下面的讨论均采用这种方式实现。动态规划之所以具有高时效，是因为它在将问题规模不断减小的同时，有效地把解记录下来，从而避免了反复解同一个子问题的现象，因而只要运用得当，较之搜索而言，效率就会有很大的提高。

动态规划的思想，为我们解决与重叠子问题相关的最优化问题提供了一个思考方向：通过迭代考虑子问题，将问题规模减小而最终解决问题。适于用动态规划解决的问题，是十分广泛的。动态规划的思想本身是重要的，但更重要的是面对具体问题的具体分析。要分析问题是否具备使用动态规划的条件，确定使用动态规划解题的子问题空间和递推关系式等，以及在(常规)内存有限的计算机上实现这些算法。下面分别就构思和实现两个方面进一步探讨动态规划这一思想。

### 二、动态规划解题的构思 ###

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

首先，要大致分析一个问题是否可能用动态规划解决。如果一个问题难以确定子问题，或问题与其子问题的特殊解之间毫无关系，就要考虑使用其它方法来解决(如搜索或其它方法等)。做一个大概的判断是有必要的，可以防止在这上面白花时间。通常一个可以有效使用动态规划解决的问题基本上满足以下几方面的特性：

1.  子问题的最优解仅与起点和终点(或有相应代表意义的量)有关而与到达起点、终点的路径无关。
2.  大量子问题是重叠的，否则难以体现动态规划的优越性。

下面以“字符识别”问题为例进行分析一般情况下动态规划思路的建立。

字符识别问题，题目大意是：在FONT.DAT中是对o(空格)、A—Z这27个符号的字形说明。对每一个符号的字符点阵，用20行每行20个“0”或者“1”表示。在另一个输入文件中，描述了一串字符的点阵图象(共N行)，但字符可能是“破损的”，即有些0变成了1，而有些1变成了0。每行固定也为20个“0”或“1”，但每一个字符对应的行可能出现如下情形：

1.  仍为20行，此时没有丢失的行也没有被复制的行；
2.  为19行，此时有一行被丢失了；
3.  为21行，此时有一行被复制了，复制两行可能出现不同的破损。

要求输出，在一个假定的行的分割情况下，使得“0”与“1”的反相最少的方案所对应的识别结果(字符串)。

在初步确定这个问题可以用动态规划思想解决之后，我认为可以考虑用数学的方法(或观点)来刻划这个问题，比如通常的最优化问题(这也是动态规划解决的主要问题)，总会有一个最优化的标准，动态规划要通过递推来实现，就要求分析确定这个状态所需要的量。比如字符识别问题，在问题规模下相当于求N行的一种分割与对应方法，因而很自然地，考虑前几行就成了一个确定状态的量。最优的标准题中已经给出，即在某种假设(包括分割方法与对应识别方法)下，使得“0”与“1”反相数最少。如果把这个度量标准看作一个函数，这实际上就是一个最优化函数(指标函数)，最优化函数的值依赖于自变量，即确定状态的量。自变量的个数(这里是一个，即行数，考虑前几行之意)，要因题而异，关键是要有效地确定状态，在这种状态下，因保证靠这些量已经能够确定最优化函数的值，即最优化函数在这些量确定的时候理论上应有确定的值，否则量是不够的或要使用其它量来刻划，而即使能够完全确定，但在建立递推关系式时发生困难，也要根据困难相应调整确定最优化函数值的自变量。而反过来，如果设定了过多的量来确定最优化函数值，那么，动态规划的效率将会大大下降，或者解了许多不必要解的子问题，或者将重叠子问题变成了在这种自变量条件下的非重叠子问题，从而大大降低效率，甚至完全失去动态规划的高效。在这个例子中，对于前L行，此最优化函数显然有确定的值。

动态规划的递推的一种重要思想是将复杂的问题分解为其子问题。因而确定子问题空间及建立递推关系式是十分重要的。根据确定最优化函数值的自变量，往往对子问题空间有着暗示的作用。通常，通过对最接近问题的这步进行倒推，可以得到这个问题规模减小一些的子问题，不断这样迭代考虑，就往往能够体会到问题的子问题空间。而在这个过程中，通过这种倒推分析，也比较容易得出这种递推关系。需要指出，这仅仅是对一些题目解题思考过程的总结，不同的题目原则上仍应区别对待。比如字符识别问题，考虑n行该最优化函数值时，注意到最终一定是按照字符分割与识别的，因而最后一个字符或者是19行，或者是20行，再或者是21行，仅这样三种可能情况，依次考虑这三种分割方法，对于切割下来的这一段对应于一个字符，对于每一种切割方案，当然应该选择最匹配的字符(否则，如果不使用反相情况最少的字符作为匹配结果而导致全局的最优，那么只要在这一步换成反相情况最少的字符，就得到比假定的“最优”更优的结果，从而导致矛盾)。在去除一个字符后，行数有所减少，而这些行去匹配字符显然也应当使用最优的匹配(可以用反证法证明，与前述类似)，于是得到一个与原问题相似(同确定变量，同最优化标准)但规模较小的子问题，与此同时子问题与原问题的递推关系事实上也得到了建立：

f\[i\]:=min\{Compare19\[i-19+1\]+f\[i-19\],Compare20\[i-20+1\]+f\[i-20\], Compare21\[i-21+1\]+f\[i-21\]\}

f\[i\]表示对前i行进行匹配的最优化函数值；

Compare19\[i\]、Compare20\[i\]、Compare21\[i\]分别表示从i行开始的19行、20行、21行与这三种匹配方式下最接近的字符的反相的“0”与“1”的个数。

初始情况，f\[0\]=0，对于不可能匹配的行数，用一个特殊的大数表示即可。当然，本题的问题主要还不在于动态规划的基本思考上(这里只是通过这个例子，讲一下对于不少动态规划问题的一种基本的思考方向)，还有数学建模(用2进制表示0、1串)等

有时虽然按上述思路得出的确定状态的量已经能够使最优化函数具有确定的值，但是在建立递推关系时发生困难，通过引入新的变量或调整已有变量，也是一条克服困难的途径。比如，NOI’97的一题“积木游戏”，题目大意是：

积木是一个长方体，已知N个有编号的积木的三边(a、b、c边)长，要求出用N块中的若干块堆成M(1≤M≤N≤100)堆，使总高度最大的高度值，且满足：

1.  第K堆中任意一块的编号大于第K+1堆中任意一块积木的编号；
2.  任意相邻两块，下面的块的上表面要能包含上面的那块的下表面，且下面的块的编号要小于上面积木的编号。

因为题目要求编号小的堆的积木编号较大，这不太自然，在不改变结果的前提下，把题目改作编号小的堆的积木编号较小，这显然不会影响到最终的高度和，而且，此时每一种合理的堆放方法可看作，按编号递增的顺序选择若干积木，按堆编号递增的顺序逐堆放置，每堆中积木依次在前一个上面堆放而最终形成一种堆放方案。使用上面一般的分析方法，很容易看出，考虑前i个木块放置成前j堆，这样，i、j两个量显然能够确定最优函数的值，然而递推关系却不易直接建立，稍作分析就会发现，问题主要出在第i块到底能否堆放到其子问题(i-1,j作变量确定的状态)的最优解方案的最后一堆上。如果考虑增加该序列最后一块的顶部的长与宽的(最小)限制这两个变量，建立递推关系并不困难，然而，很明显，递推过程中大量结果并未被用到，这就人为地扩大了子问题空间，不仅给存储带来麻烦，而且效率也很低。其实，建立递推需要的仅仅是在子问题解最后一堆顶部能否容纳当前积木块，而题中可能产生的这种限制性的面最多仅有3\*100+1(无限制)=301种情况，这样在多引入一个“最后一堆顶部能够容纳下第k种面的要求”这个量后，递推关系只要分当前块另起一堆、当前块加在前一堆上(如果可能的话)和当前块不使用这三种情况就可以了。

此外，有些问题可能会出现仅靠这种调整递推关系仍难以建立，这时，通过增加其它量或函数来建立递推关系式也是一种思考方向(类似于数学归纳法证明时的“加强命题”)。因为，用动态规划解题的一个重要特征是通过递推，而递推是利用原有结果得到新结果的过程。如果在理论上可以证明，一个难以直接实现递推的问题可以通过引入新的递推关系，同时将两者解决，这看起来把问题复杂化了，而实际上由于对于每一步递推，在增加了解决的问题的同时也增加了条件（以前解决的值），反而使递推容易进行。举例说明，“多边形”一题，大意如下：

有一个多边形（N边形），顶点上放整数，边上放“+”或“\*”，要寻找一种逐次运算合并的顺序，通过N-1次运算，使最后结果最大。

如果单纯考虑用MAX\[I,L\]，从I开始进行L个运算所得的最大值，则难以实现递推，而根据数学知识，引入了MIN\[I,L\]为从I开始进行L个运算所得的最小值，在进行递推时，却能够有效地用较小的I，L来得到较大时的结果，从而事实上同时解决了最小值与最大值两个问题。

递推关系式如下：(考虑I从1到N,L从1到N-1)

考虑t(最后一步运算位置)从0到L-1：

如果最后一步运算为“+”则：

**min(i,L)=****最小值****\{min(i,t)+min((i+t+1-1) mod N+1,L-t-1)\}**

**max(i,L)=****最大值****\{max(i,t)+max((i+t+1-1) mod N+1,L-t-1)\}**

如果最后一步运算为“\*”则：

**min(i,L)=****最小值****\{min(i,t)\*min((i+t+1-1) mod N+1,L-t-1),**

**min(i,t)\*max((i+t+1-1) mod N+1,L-t-1),**

**max(i,t)\*min((i+t+1-1) mod N+1,L-t-1),**

**max(i,t)\*max((i+t+1-1) mod N+1,L-t-1)\}**

**max(i,L)=****最大值****\{min(i,t)\*min((i+t+1-1) mod N+1,L-t-1),**

**min(i,t)\*max((i+t+1-1) mod N+1,L-T-1)**

**max(i,t)\*min((i+t+1-1) mod N+1,L-t-1),**

**max(i,t)\*max((i+t+1-1) mod N+1,L-t-1)\}**

此外，动态规划通过递推来实现，因而问题与子问题越相似，越有规律就越容易进行操作。因而对于某些自身的阶段和规律不怎么明显的问题，可以通过一个预处理，使其变得更整齐，更易于实现。例如，ACM’97亚洲赛区/上海区竞赛一题“正则表达式(Regular Expression)的匹配”问题，题目大意是：

正则表达式是含有通配符的表达式，题目定义的广义符有：

1.  . 表示任何字符
2.  \[c1-c2\] 表示字符c1与c2间的任一字符
3.  \[^c1-c2\] 表示不在字符c1与c2间的任一字符
4.  \* 表示它前面的字符可出现0或多次
5.  \+ 表示它前面的字符可出现一次或多次
6.  \\ 表示它后面的字符以一个一般字符对待。

对一个输入串，寻找最左边的与正则表达式匹配的串(相同条件下要最长的)。这里如果不作预处理，则有时一个广义符可对应多个字符，有时又是多个广义符仅对应一个字符，给系统化处理带来很多麻烦。因而有必要对正则表达式进行标准化，使得或者某个结点仅对应一个字符，或者用一特殊标记表明它可以重复多次。定义记录类型：

NodeType=Record

StartChar: Char; \{开始字符\}

EndChar: Char; \{结束字符\}

Belong: Boolean \{是否属于\}

Times: Boolean; \{False: 必须一次; True:可以多次，也可以不出现\}

End;

对输入数据预处理之后，建立递推关系就不太困难了。用Pro\[i,j\]表示前i

个正则表达式结点对以第j个字符为终点的子串的匹配情况(True/False)，对于为True的情况，同时指明此条件下最先的开始位置。如果第i个正则表达式结点是仅出现一次的，那么，如果它与第j个字符不匹配，则该值为False，否则，它与Pro\[i-1,j-1\]相同。(初始时Pro\[0,x\]=True)。如果它是可重复多次的，那么它可以被解释成0个或多个字符。在它自身与相应位置的0个或多个字符匹配的条件下依次考虑这些可能情况，只要其中含True，则Pro\[i,j\]为True，同时记录下这些达到True的情况中起点最先的。按此递推，直到i达到结点个数。

### 三、动态规划实现中的问题 ###

动态规划解决问题在有了基本的思路之后，一般来说，算法实现是比较好考虑的，但有时也会遇到一些问题，而使算法难以实现。动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推，相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题。

对于这个问题，我认为，可以考虑从以下一些方面去尝试：

一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因题而异，进行分析。另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的，而且处理速度也有一些提高。但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做，在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时，是很有意义的。

但有时，即使采用这样的方法也会发现空间溢出的问题。这时就要分析，这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题，动态规划递推在处理后面的内容时，前面比较远处的内容实际上是用不着的。对于这类问题，在已经确信不会再被使用的数据上覆盖数据，从而使空间得以重复利用，如果能有效地使用这一手段，对于相当大规模的问题，空间也不至于溢出。（为了求出最优方案，保留每一步的决策仍是必要的，这同样需要空间。）一般地说，这种方法可以通过两种思路来实现。一种是递推结果仅使用Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过复制覆盖到Data1之上，如此反复，即可推得最终结果。这种做法有一个局限性，就是对于递推与前面若干阶段相关的问题，这种做法就比较麻烦；而且，每递推一级，就需要复制很多的内容，与前面多个阶段相关的问题影响更大。另外一种实现方法是，对于一个可能与上N阶段相关的问题，建立数组Data\[0..N\]，其中各项即为与原Data1/Data2相同的内容。这样不采用这种内存节约方式时对于下标K的访问只要对应成对下标K mod (N+1)的访问，就可以了。与不作这种处理的方法相比，对于程序修改的代码很少，速度几乎不受影响(用电脑做MOD运算是很快的)，而且需要保留不同的阶段数也都能很容易实现。这种手段对不少题目都适用，比如：NOI’98的“免费馅饼”，题目大意是：

有一个舞台，宽度W格(1≤W≤99的奇数),高度H格(1≤H≤100)，游戏者在时刻0时位于舞台正中，每个单位时间可以从当时位置向左移2格、向左移1格、保持不动、向右移1格或者向右移2格，每个馅饼会告知初始下落的时间和位置以及下落速度(1秒内下移的格子数)和分值。仅在某1秒末与游戏者位于同一格内的馅饼才被认为是接住的。求一种移动方案，使得分最大。注意：馅饼已按初始下落时间排序。

从问题来看，想到动态规划并不是很困难的。但是，题中规定初始下落时间从0到1000，而且考虑下落到最后可能时间要到1100左右,而宽度可达99，以时间-位置作为状态决定因素进行递推，速度不会慢，但如果采用初始数据经预处理后的结果(即在何时到何地可得多少分的描述数组)用一个数组，动态规划递推用一个数组，记录每步决策用一个数组，因得分题中未指出可能的大小，如果采用前两个Longint型，最后一个Shortint型，所须内存约为1100\*99\*9字节，即约957KB，这显然是不可能存得下的。但是注意到在进行递推时，一旦某一个(时间，位置)对应的最大分值一确定，这个位置的原始数据就不再有用，因而两者可以合二为一，从而只要1100\*99\*5字节，即约532KB。这样对于题目规模的问题就勉强可以解决了。 当然，如果更进一步思考，其实这个问题中递推是仅与上一个时间有关的，而馅饼实际上仅使用了当前位置的值。由于初始下落时间已经排序，那么当读到初始下落时间晚于当前处理时间时，就不必马上读入。为了避免重复和无规律地读盘和内存开销过大，只要记录下当前之后约100个时间单位内的情况就可以了，使用前面所说的循环使用内存的方法，只要101\*99\*4+99\*2\*2=40392字节，不到40KB，而对于每一个时间仅需99个shortint存储决策即可,就算把问题规模提高到3000或者4000个时间单位也能顺利出解。 (源程序见附录中的程序5)

当采用以上方法仍无法解决内存问题时，也可以采用对内存的动态申请来使绝大多数测试点能有效出解(而且，使用动态内存还有一点好处，就是在重复使用内存而进行交换时，可以只对指针进行交换，而不复制数据)，这在竞赛中也是十分有效的。

### 四、总结 ###

动态规划是一种重要的程序设计思想。但是，由于它没有确定的算法形式，因而也就有较大的灵活性，但它的本质却具有高度的相似性。所以，学习和使用这一思想方法，关键在于在理解和把握其本质的基础上灵活运用。本文虽然谈到了一些思想方法，但这些仅是对一些较普遍问题的讨论，针对具体问题进行具体分析建立数学模型才是最重要而关键之处。