动态规划的优化及应用

1动态规划的优化及应用广东北江中学卢彦丞关键词：动态规划优化应用目录序…………………………………………………………………2[一]动态规划的优化和特殊技巧………………………………31.改变状态表示……………………………………………32.预处理，必要时进行两次动态规划……………………73.针对“双向问题”的优化………………………………84.其他优化…………………………………………………125.按特殊顺序进行动态规划………………………………156.把最优值问题转化为判定问题…………………………16[二]动态规划的应用……………………………………………181.计数………………………………………………………182.一些图论问题……………………………………………213.求第K优解………………………………………………21[三]后记…………………………………………………………242序：说起动态规划，大家一定不会陌生。这是因为自从21世纪伊始，各类信息学竞赛中的动态规划逐渐成为了主要题型之一。但是，越来越多的证据表明，动态规划并不是一件容易的事。而本文主要论的就是动态规划如何优化，以及它在一些什么地方有用武之地。也就是说，这篇论文讲的是关于“动态规划进阶”的。至于动态规划的基础知识，可以查阅有关资料，这里不再赘述。注：在本文，例题列出状态转移方程后不再附标程，因为对于动态规划题来说，知道了状态转移方程后就可以自己写出程序了。3[一]动态规划的优化和特殊技巧也许大家会问，“动态规划算法是一种非常优的多项式时间算法，用得着优化吗？”“搜索需要优化，动态规划也需要吗？”差矣。虽然动态规划是一种多项式时间、多项式空间的算法，但是弄不好也会超时、爆空间。如，一道动态规划题，规模是1=n=1000，如果你写出个O(n3)的状态转移方程，不超时才怪呢！而如果把它优化成O(n2)的话，就基本上不会超时了。如果方程正确的话，你就能通过这道题了！1.改变状态表示众所周知，动态规划的核心是状态转移方程，而状态转移方程的关键是阶段的划分和状态的表示。所以说，状态表示得好不好，会决定着动态规划的其他一切因素，正可谓“牵一发，动全身”。有时候，改变一下状态表示，就可以在状态转移时，只让O(1)个状态转移到该状态，从而使时、空复杂度都减少一维。下面举几个例子：[例1]花店橱窗布置（IOI99）题目简述：有V个花瓶按顺序排成一行，最左边是1号，最右是V号。你有F束花要插在花瓶中，花束的编号决定了花束在花瓶中的排列顺序。即如果ij，则花束i所在的花瓶必须在花束j所在的花瓶的左边。如果花瓶数大于花束数，则多余的花瓶必须空置。每个花瓶最多只能放一束花。第i束花插在j号花瓶中的美学值为Ai,j。整个摆放方式的美学值为所有花束在所插花瓶中的美学值之4和。现在给出一个Ai,j的矩阵，求具有最大美学值的摆放方式。（1=F=V=100,-50=Ai,j=50）分析：由“花束的编号决定了花束在花瓶中的排列顺序”可知该问题具有“无后效性”，并且很容易得出该问题的“最优化原理”，所以这是一道动态规划题。以花束划分阶段，设fi,j代表前i束花插进前j个花瓶中、并且第i个花束必须插进第j个花瓶中能产生的最大美学什，则可列出以下的状态转移方程：……………………（1）f[F,V]即为最大美学值。但是，这是个O(FV2)的方程，如果把F、V的范围调成1000会怎样？再说，虽然F、V的范围是100，但那是1999年的题啊！你以为那时候的机子有现在的这么快吗？弄不好就超时了！看来需要进行一点优化。不如我们重新考虑怎么样？以花瓶为阶段，设fi,j代表前i束花插进前j个花瓶中，但第i束花不一定插进第j个花瓶能产生的最大美学值，则可列出以下的状态转移方程：……………………（2）f[F,V]即为最大美学值。5稍微对时间复杂度有点了解的人就会发现，（2）比（1）整整降了一维：（2）的时间复杂度为O(FV)。这时，这个方程不仅能轻松应付规模为100的小数据，应对那些更大的数据也不在话下了！其实，如果把一个类似于“”的式子代入（1）也可以变换出（2），但何必那么麻烦呢？还不如脑筋一个大转弯，重新考虑来得更爽一些呢！再来看一个很典型的例子：[例2]多源多汇最短路问题题目简述：给你一个带权（可能有负权，但一定没有负环）无向图/有向图，计算出每对顶点间的最短距离。分析：这是一个很典型的问题，现在我们可以用Floyd-Warshall算法求解。但是，在不会Floyd-Warshall算法的情况下或者在该算法被发明之前怎么办？换句话说，Floyd-Warshall算法是如何得到的？……好吧，看看这道题，发现它有点“隐隐约约”地有首最优子结构，这“助长”了我们用动态规划的“苗头”。用最短路径的边的条数划分阶段：设fk,i,j表示经过k条边、从i到j的最短路长度。易得到下面的状态转移方程：注：n是顶点数，ai,j为从i到j的边权，边不存在用+∞表示，6下同。最后顶点i到j的最短路长度为。易看出，这是个O(n4)（即O(V4)）的算法！这还不如直接以每个顶点为源点来一次Bellman-Ford算法来得快呢，那样还可以有O(V2E)。是不是动态规划有问题？事实上，动态规划的思想没有问题，是你状态表示有问题！既然有问题，就换一种角度去想吧！设fk,i,j表示从i到j，路径中间顶点编号不超过k的最短路长度。那么状态转移方程就可以改写如下：看吧，O(n3)（即O(V3)）的算法！都说了，谁说动态规划不行呢？事实上，上面的动态规划方法就是大名鼎鼎的Floyd-Warshall算法，也是“任意图”多源多汇最短路的最优算法（其实说准确点是稠密、有负权边的图）。不仅这些例子，在下文可以看到，这种优化应用得十分广，更多的例子也用到了这种方法降维。2.预处理，必要时进行两次动态规划在动态规划中，常常不可避免地用到某些需要另外计算的量，而7每次都计算这些量未免会大大增加动态规划算法的时间复杂度。就你在统计工作中要多次用到你们班期末考试的平均分，你不可能每次要用到的时候都傻傻地拿成绩单重新算一遍吧？你应该会先把算好了的平均分记下来的。这就对了，何不把这些量先预处理算出来，尼？如果预处理时也需要动态规划，那就正好是所谓的“两次动态规划”了。下面这个例子比较好理解，相信大家看完这个例子都知道动态规划的“预处理”了吧！[例3]IOI2009“葡萄干问题”题目简述：有一个矩形面包，被分割成了n行m列共n*m个方格。现在要把面包切成如上所述的n*m个小正方形。第i行第j列的方格上有ai,j个葡萄干。你每一次可以选择一块矩形面包（第一次是整块，以后的每次是切好的某一块），沿着方格的分界线把它切成两块矩形面包。然后你切这一刀得到的报酬等于切之前的这块面包上所含葡萄干总数。问怎样切才会获得最大报酬？分析：此题可以用动态规划的思想求解。用f[i,j,k,l]表示把左上角为(i,j)，右下角为(k,l)的矩形切成单位方格所得到的最大报酬（i=k,j=l）。规划方程如下：其中w[i,j,k,l]为左上角为(i,j)，右下角为(k,l)的矩形上葡8萄干的个数。最终f[1,1,n,m]即为最优值。（动态规划顺序为按k-i或l-j的递增顺序）那么w如何计算？我们发现，不可能一个个累加，这样准会杯具。仔细一想，原来这个w数组可以预先算出来的（即预处理），并且可以用动态规划的方式算出来！至此我们的思路就清晰了！计算w数组的方程如下：至此这道题的时间复杂度就是O(n2m2)+O(n2m2)=O(n2m2)！（如果你一个个累加，说不定连O(n4m4)都来了！）没错了，作一下预处理，就能省去大量重复计算！3.“双向问题”中，先解决“单向问题”，再枚举相遇点动态规划一般是用递推实现的。但你有没想过，不仅是递推的最后一个结果有用，而是每个结果都可以用上？尤其在“双向问题”中，这种技巧更为有用？下面就举个简单的例子吧。[例4]牛郎织女相会问题题目简述：七夕快到了，恶毒的王母娘娘又想出了新招法对付牛郎织女。她用钱买通了天下的喜鹊，要它们搭桥时弄成不同高度，把桥弄得起伏不平；这样，牛郎织女过桥时就需要耗费大量能量了。为了简化问题，假设有N只喜鹊搭桥，从牛郎那边的起点到织女那边的起点，依次标号从1到N，第i只喜鹊高度为hi。可是，王母娘娘的阴谋暴露了，牛郎和织女都知道了这件事，并且知道了每只喜鹊的高9度；虽然他们斗不过王母娘娘。他们知道，只有准备足够的能量，才能了结一年来的苦苦相思。他们都知道，牛郎从第i只喜鹊走/跳到第j只喜鹊（必须满足ij，即不能走回头路）所耗费的能量为ai,j，而织女从第i只喜鹊走/跳到第j只喜鹊（必须满足ij，她也不能走回头路）所耗费的能量为bi,j。（这里的ai,j是某个关于|j-i|、hi以及hj的函数，bi,j也是）他们可以在任意一只喜鹊上相遇（他们到达同一只喜鹊即为相遇）。请计算他们所需最小能量（牛郎的加织女的）。分析：这是一个“双向问题”，需先转化成“单向问题”。先计算牛郎从1号喜鹊到其他各喜鹊的所需最小能量。设从1号到i号的最小花费能量为f[i]，则时间复杂度为O(n2)。（别奢望用“1.改变状态表示”的方法把它优化成O(n)，这是不可能滴~因为这题不像那里的题，有更好的状态表示方法）同理，计算织女从N号喜鹊到其他各喜鹊的所需最小能量。设从N号到i号的最小花费能量为g[i]，则10时间复杂度也是O(n2)。最后枚举相遇点，求出最小总花费，即结果为。而使f[i]+g[i]最小的i值即为最佳相遇点。这一步时间复杂度为O(n)。总复杂度为O(n2)+O(n2)+O(n)=O(n2)。上面所说的是最优解法。但是，更多人会想到这样的方法：先枚举相遇点（O(n)），然后对每个相遇点用上面的方法求出最小总花费，再更新最优值，这样造成了大量重复计算，总时间复杂度为O(n)×O(n2)=O(n3)。我个人是不推荐这种浪费电的做法的。你看，我们现在倡导“低碳”生活，而这种方法为了算得同样一个结果，却比最优算法多用了N倍时间，这样对计算机来说不是浪费电和产生无谓的热吗？如果人人都这样浪费，不就是会加速“2012”的来临吗？对不起，扯远了。反正使用高效算法是百利而无一弊的，只是看你有没有想到。下面这道广东省省赛题，是和前一题异曲同工的。[例5]方块游戏（GDOI2008）题目简述：有一种积木，可以看成是单位边长的正方体块。一个“高木”就是一个或多少积木垂直叠放在一起形成的，高度为叠放积木块的个数。多个“高木”从左到右排列起来形成一个山脉，从左到右第i个“高木”高度为H[i]。山峰是满足以下条件的山脉：存在一个整数k∈[2,N-1]使得对于所有位置i都有：H[i]H[i-1],1i=kH[i]H[i+1],k=iN11（N为山脉中“高木”的个数）有一种超级工具，每次操作可以给山脉中一段连续区间各位置都叠放上一块积木，使得高度同时增加1个单位。只用这种超级工具，把一个给定的山脉改造成山峰至少需要操作几次？（积木不会供应不足）分析：先考虑一个“单向问题”，如果改造的目标是从1到N高度严格递增所需最少步数。我们容易发现以下特点：①无序性：对于一个方案，交换任意两个操作的执行次序不会改变方案的最终结果。②局部不变性：进行一次从L到R的“高度加1”操作不会改变[L,R]区间原有的曲线趋势（如在严格递增的区间上操作一次，这个区间还是严格递增的）③由①可以推出，我们可以先满足从1到i高度严格递增，再满足从1到i+1高度严格递增。④并且第一个位置上的高度没必要增加。⑤任意一个最优方案，都可以把所有操作都改成[x,N]的形式（即操作右边界改为序列结尾）。于是，我们可以得到该“单向问题”的状态转移方程：注：当H[i]H[i-1]时只需把[1,i-1]区间内的所有操作的右边界由i-1改为i即可；否则，除作上述改动外，还需添加12(H[i-1]-H[i]+1)个左、右边界都是i的操作。同理，另一个“单向问题”——目标为从1到N高度严格递减——的状态转移方程为那么怎样把它们