动态规划的优化及应用

1 动态规划的优化及应用 广东北江中学 卢彦丞 关键词：动态规划 优化 应用

目录 序 „„„„„„„„„„„„„„„„„„„„„„„„„2 [一] 动态规划的优化和特殊技巧 „„„„„„„„„„„„3 1. 改变状态表示 ……………………………………………3 2. 预处理，必要时进行两次动态规划 ……………………7 3. 针对“双向问题”的优化 ………………………………8 4. 其他优化 …………………………………………………12 5. 按特殊顺序进行动态规划 ………………………………15 6. 把最优值问题转化为判定问题 …………………………16 [二]动态规划的应用 „„„„„„„„„„„„„„„„„18 1. 计数 ………………………………………………………18 2. 一些图论问题 ……………………………………………21 3. 求第K优解 ………………………………………………21 [三]后记 „„„„„„„„„„„„„„„„„„„„„„24 2

序： 说起动态规划，大家一定不会陌生。这是因为自从21世纪伊始，各类信息学竞赛中的动态规划逐渐成为了主要题型之一。但是，越来越多的证据表明，动态规划并不是一件容易的事。而本文主要论的就是动态规划如何优化，以及它在一些什么地方有用武之地。也就是说，这篇论文讲的是关于“动态规划进阶”的。至于动态规划的基础知识，可以查阅有关资料，这里不再赘述。

注：在本文，例题列出状态转移方程后不再附标程，因为对于动态规划题来说，知道了状态转移方程后就可以自己写出程序了。 3

[一] 动态规划的优化和特殊技巧 也许大家会问，“动态规划算法是一种非常优的多项式时间算法，用得着优化吗？”“搜索需要优化，动态规划也需要吗？”差矣。虽然动态规划是一种多项式时间、多项式空间的算法，但是弄不好也会超时、爆空间。如，一道动态规划题，规模是1<=n<=1000，如果你写出个O(n3)的状态转移方程，不超时才怪呢！而如果把它优化成O(n2)的话，就基本上不会超时了。如果方程正确的话，你就能通过这道题了！

1. 改变状态表示 众所周知，动态规划的核心是状态转移方程，而状态转移方程的关键是阶段的划分和状态的表示。所以说，状态表示得好不好，会决定着动态规划的其他一切因素，正可谓“牵一发，动全身”。有时候，改变一下状态表示，就可以在状态转移时，只让O(1)个状态转移到该状态，从而使时、空复杂度都减少一维。下面举几个例子： [例1] 花店橱窗布置（IOI99） 题目简述：有V个花瓶按顺序排成一行，最左边是1号，最右是V号。你有F束花要插在花瓶中，花束的编号决定了花束在花瓶中的排列顺序。即如果i在的花瓶的左边。如果花瓶数大于花束数，则多余的花瓶必须空置。每个花瓶最多只能放一束花。第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只喜鹊（必须满足i而织女从第i只喜鹊走/跳到第j只喜鹊（必须满足i>j，她也不能走回头路）所耗费的能量为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]，则