动态规划周谷越.docx
《动态规划周谷越.docx》由会员分享，可在线阅读，更多相关《动态规划周谷越.docx（71页珍藏版）》请在冰点文库上搜索。
动态规划周谷越
信息学竞赛中的动态规划专题
哈尔滨工业大学周谷越
【关键字】
动态规划动机状态典型题目辅助方法优化方法
【摘要】
本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。
通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。
并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。
纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。
【目录】
1.动态规划的动机和基本思想
1.1.解决重复子问题
1.2.解决复杂贪心问题
2.动态规划状态的划分方法
2.1.一维状态划分
2.2.二维状态划分
2.3.树型状态划分
3.动态规划的辅助与优化方法
3.1.常见辅助方法
3.2.常见优化方法
4.近年来Noi动态规划题目分析
4.1Noi2005瑰丽华尔兹
4.2Noi2005聪聪与可可
4.3Noi2006网络收费
4.4Noi2006千年虫
附录参考书籍与相关材料
1.动态规划的动机和基本思想
首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。
1.1解决重复子问题
对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。
这类问题的共同点是小问题和大问题的本质相同。
很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑（log2n/k）。
而考虑下面这个问题：
USACO1.4.3NumberTriangles
【题目描述】
考虑在下面被显示的数字金字塔。
写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。
每一步可以走到左下方的点也可以到达右下方的点。
7
38
810
2744
45261
在上面的样例中，从7到3到8到7到5的路径产生了最大和：
30。
【输入格式】
第一个行包含R（1<=R<=1000）,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
【输出格式】
单独的一行包含那个可能得到的最大的和。
【样例输入】
5
7
38
810
2744
45261
【样例输出】
30
显然，我们同样可以把大问题化成小问题来解决。
如样例中最底层的6就可以从次底层的两个4走来，假设分别知道走到次底层的两个4的最优解，那么取其中较大的加上6就是走到最底层的6时的最优解。
然而次底层的两个4还可以走向最底层的2和1，这样就产生了重复的子问题。
动态规划的第一类动机就是为了要避免这种重复运算。
事实上，子问题的个数是确定的，只要我们能够把已经计算过的子问题记录下来，再下次需要时直接使用，便可以大大提高程序的效率。
下面介绍一下动态规划的相关概念。
首先动态规划是来解决最优化问题的，再进一步说就是解决最优化问题中的多阶段决策问题。
以下是动态的定义内容，在各种基础书籍上都有相关讲解，在此仅列出，不做累述。
状态（State）：
表示事物的性质，是描述动态规划中的单元的量。
阶段（Stage）：
阶段是一些性质相近的状态集合。
决策（Decision）：
每个阶段做出的某种选择性行动，是程序所需要完成的选择。
状态转移方程（Equal）：
是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是动态规划的核心。
初始状态：
由已知能够确定的状态。
目标状态：
表示解或能够转化为解的状态。
总体看来，由初始状态经过若干阶段通过若干决策推出目标状态的过程就是动态规划。
下面我们就NumberTriangles一题对这些概念对号入座：
首先确定状态，用F[I,J]表示从顶层走到第I行第J列的点能取得的最大和。
显然每一层为一个阶段。
而对于走到每一个非顶层点的情况来说，最多都只可能由它上方的点或左上方的点走来。
则有状态转移方程：
F[I,J]=Max（F[I-1,J],F[I-1,J-1]）+A[I,J]；初始状态为F[1,1]=A[1,1]；目标状态为F[N,K]，其中K∈[1,N]。
要求输出的解则是Max{F[N,K]}，其中K∈[1,N]。
时空复杂度均为O（N2）。
这里给出程序主干部分：
F[1,1]=A[1,1]
ForI=2toNDo
ForJ=1toIDo
IfF[I-1,J]>F[I-1,J-1]Then
F[I,J]=F[I-1,J]+A[I,J]
Else
F[I,J]=F[I-1,J-1]+A[I,J]
接下来我们从理论上来讨论使用动态规划的条件。
对于一种状态划分的方法来说，状态只与状态本身的性质有关，而与如何达到该状态等其他条件一概无关的性质叫做无后效性。
由于存在无后效性，决策只能从决策本身的性质来确定，使得某一阶段的状态只与它所在阶段的前一阶段的状态有关。
可以看出，存在无后效性是应用动态规划的前提条件。
而考虑动态规划的正确性时，问题则需要满足最优子结构。
所谓最优子结构，即当前一阶段的状态最优时，通过状态转移方程得到的状态也能达到最优。
理论上看，无后效性和最优子结构是使用动态规划时的两个基本条件，而具体应用动态规划时更多凭借的是经验。
下面再引出一道经典题目做一下分析：
ACM/ICPCShanghai2001Skiing
【题目描述】
滑雪是一项很受欢迎的体育运动，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡。
我们想知道载一个区域中最长的滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子：
12345
161718196
152425207
142322218
131211109
我们可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
在上面的例子中，一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。
事实上，这是最长的一条。
【输入格式】
输入的第一行表示区域的行数R和列数C（1<=R,C<=500）。
下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
【输出格式】
输出最长区域的长度。
【样例输入】
55
12345
161718196
152425207
142322218
131211109
【样例输出】
25
有了前面的例子，不难看出，每个点可以由四个方向中比它高的点滑到。
设DX={0,1,0,-1}，DY={1,0,-1,0}，F[I,J]表示滑到第I行第J列的点时存在的最长滑坡长度，则有状态转移方程：
F[I,J]=Max{F[I+DX[K],J+DY[K]]}+1，其中要求满足第I+DX[K]行第J+DY[K]列的点存在且高度比第I行第J列的点的高度高。
我们可以按照深度优先搜索的方式计算F，并利用二维数组Arr记录计算过的F值，下面同样给出程序主干部分：
FunctionF（IntI,IntJ）
{
IfArr[I,J]>0Then
ReturnArr[I,J]
IntP,Ans=0
ForP=1to4Do
If（（I+DX[P],J+DY[P]）InMap）And（H[I+DX[P],J+DY[P]]>H[I,J]）Then
If（AnsAns=F[I+DX[P],J+DY[P]]
Arr[I,J]=Ans+1
ReturnArr[I,J]
}
同样是动态规划，是什么使得两道题目代码的主干部分相差巨大呢？
这里讨论一下动态规划的两种实现形式——递推和记忆化搜索。
首先，可以说所有用递推实现的动态规划均可以利用记忆化搜索实现。
而某些题目之所以可以用递推求解，是因为这类题目同一阶段的状态表示上有很大的相关性，比如数字矩阵中某一行或列，这使得我们可以计算一个阶段的所有状态后再计算下一状态。
而某些题目中利用动态规划划分的同一阶段的状态表示上没有多大相关性，比如Skiing里面的状态，从某点做起点每滑动一步为一个阶段，我们无法用一个准确的可以直接利用的集合将一个阶段中的状态表示出来，只能从已知状态去找和它相关联的状态。
对于Skiing我们已知的是目标状态（即四面都不比该点高的点），通过边界条件（即四面都比该点高的最优值为1），便可以进行记忆化搜索。
利用递推实现动态规划时，单位操作时间小，可以方便地使用一些优化；而利用记忆化搜索实现动态规划时，单位操作时间大，但可以避免计算一些不必要的状态。
总地来说，相比于用状态空间搜索的方法解决这类存在重复子问题的题目，使用动态规划增大了空间的开销，但提高了时间效率。
1.2解决复杂贪心问题
接下来，进入下一话题。
我们考虑一下我们熟知的贪心算法和动态规划的关系，我看过很多写贪心算法和动态规划之间区别的材料，在这里我们不谈这个，而是要讨论动态规划与贪心算法之间的联系。
如果我们把每一步贪心作为一个阶段，那么可以认为每个阶段只有一个状态，再把贪心策略看作状态转移方程，那么这样是否也是一种“动态规划”呢？
实际上，它们二者之间的差别就在数据的维护上，有很多贪心问题在采取一次贪心策略之后要对数据进行全盘的维护，而我们讲的动态规划一般没有这个步骤。
而这个维护的目的是什么呢？
是为了保证正确性，和动态规划中的最优子结构的目的一样，那么就说明目前的状态划分不具有最优子结构，那么我们是否能够通过改变状态的划分方法来代替这个维护并使新划分的状态具有最优子结构呢？
这里直接给出结论：
对于某些分步讨论的贪心决策问题，我们可以通过扩展状态使之能够用动态规划解决。
扩展出的状态的作用就是为了保证正确性，也就是保证最优子结构。
举一个简单的例子：
给出N个数，要从其中取M个求和，并使和尽量大。
这明显是一个贪心可解的问题，把数字从大到小排序后取前M个求和即可。
那么我们同样也可以扩展出一部分状态。
我们设F[I,J]表示前I个数字中取了J个数字得到的最大和，则有：
F[I,J]=Max（F[I–1,J],F[I-1][J-1]+A[J]）。
那些贪心算法并不用考虑的“多余”状态就是扩展出的状态，举个实例来说明：
N=5,M=3时，A[]={1,2,3,4,5}。
那么显然1和2都不会被取到，但数组F中的F[1,1],F[2,1]和F[2,2]都是由1和2组成的状态，从贪心的角度看，它们就是多余的，就是为了使用动态规划扩展出来的状态。
当然，就这道题目来看，贪心算法无论是从思维角度、编程角度还是时空复杂度角度都明显优于动态规划。
HCPCSpring2007HurdlesRace
【题目描述】
自从刘翔在雅典夺得110米栏冠军之后，国人对跨栏比赛的关注程度大大提高。
阿月和同学们经常在一起讨论刘翔需要用多少步来完成比赛，大家对该问题的意见不太一致，经常为此争论不休。
我们下面定义这样一种跨栏比赛：
tl表示起点到终点的距离（可能不是110）；
sl表示刘翔一步可以跨越的最大距离（我们规定刘翔每次跨越的距离必需是整数）；
fl表示第一个栏到起点的距离（fln表示栏的数目；
d表示每两个栏之间的距离（我们保证最后一个栏到起点的距离小于tl）；
每次跨栏的时候，刘翔都要保证栏的位置恰好在他跨越距离的正中间。
求在这些条件下刘翔完成比赛所需要的最小步数。
【输入格式】
输入包括五个正整数，分别表示tl,sl,fl,n,d（tl不超过10000，sl不超过10）。
【输出格式】
输出包括一个整数，即刘翔完成比赛所需要的最小步数。
【样例输入】
110320105
【样例输出】
41
【样例说明】
起点到跨过第一个栏至少需要8步，之后每跨一个栏至少需要2步，从跨过最后一个栏到终点至少需要15步。
由于只有跨栏的那步有限制条件，其它步没有，故有了贪心思想——跨栏那步要尽可能的大。
通过分情况讨论后得到解：
跨第一个栏之前的步数+栏的个数+跑2个栏之间路程需要的步数×（栏的个数-1）+最后一个栏需要的步数。
需要考虑的特殊情况只有跨第一个栏的步长未必可以达到跨其它栏的步长。
当然，如果比赛的时候可以快速地想到这个方法是最好不过的。
实际上，使用动态规划更容易建立方程。
设F[I]表示到达i位置所需要的最小步数，则有F[i]=min{F[I-K]+1}，K=1..sl，其中I-K到I之间没栏；而有栏时，F[I]=min{F[I-2*sp]+1,F[I]}，sp为栏到i点距离。
AsyzOI2007营养膳食
【题目描述】
阿月正在女朋友宁宁的监督下完成自己的增肥计划。
为了增肥，阿月希望吃到更多的脂肪。
然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。
阿月通过研究发现：
真正的营养膳食规定某类食品不宜一次性吃超过若干份。
比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。
阿月想要在营养膳食的情况下吃到更多的脂肪，当然阿月的食量也是有限的。
【输入格式】
输入第一行包含三个正整数n（n≤200）,m（m≤100）和k（k≤100）。
表示阿月每顿饭最多可以吃m份食品，同时有n种食品供阿月选择，而这n种食品分为k类。
第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。
接下来n行每行包括2个正整数，分别表示该食品的脂肪指数ai和所属的类别bi，其中ai≤100，bi≤k。
【输出格式】
输出一个数字即阿月可以吃到的最大脂肪指数和。
【样例输入】
663
332
151
152
102
152
102
53
【样例输出】
60
用贪心算法解决，就是把食品按脂肪指数排序后，在满足约束条件的情况下从大的开始吃，每吃一个更新一下约束条件。
而用动态规划思想解决的话，可以设F[I,J]表示前I类食品一共吃J份能够获得的最大脂肪数和。
则有F[I,J]=Max{F[I-1,K]+G[I,J-K]}，其中G[I,J]表示第I类食品种脂肪数最大的J份的和（也是要排序的）。
Noip1999旅行家的预算
【题目描述】
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。
给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）。
每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=l,2,...,N）。
如果无法到达目的地，则输出“Nosolution”。
否则输出最小费用，计算结果四舍五入至小数点后两位。
【样例输入】
275.611.927.42.82
1102.02.9
2220.02.2
【样例输出】
26.95
我们假设现在在第I站，那么可知在该站加满油可以到达的最远距离。
如果在这个范围内存在一个加油站J，它的价格比I便宜，那么只要把油加到刚好能到达第一个出现的J即可；否则就在I加满油，选择范围内最便宜的加油站J，开到J再做决策。
如果觉得这个方法不是很好想的话，就用动态规划实现之。
设F[I,J]表示到达第I个加油站油量为J需要的最小费用，则有F[I,J]=Min{F[I-1,J-K-G（I-1,I）]+K*A[I]}，其中G（I-1,I）表示第I个加油站和前一个加油站间的距离，A[I]表示第I个加油站的油价。
对于以上三道题目，实现贪心更容易，而想到动态规划更容易（前提是对动态规划足够熟练），可以根据实际情况选择合适的算法。
下面再给出两个相对复杂的题目。
AsyzOI2005雇工
【题目描述】
一中搬到新校舍，值得庆祝。
但我们亲爱的电教老师FJ（FengJunnotFarmerJohn）却遇到了个麻烦事。
科技馆还没完全建好，需要雇人来完成一些后续工作。
现在的行情是这样的：
你雇佣一个人得给A元，解雇一个人得给人家B元（精神损失费），当然还有工资，每月K元。
有一系列工作，需要N月来完成。
当然，不是每个月都需要相同的人数。
可是当你雇佣一个雇工，不管他干不干活，都得给他工资（吃大锅饭）。
说明一下：
到期的时候是不用付精神损失费的。
请你帮帮FJ老师，他心系学校，绝对要为一中省钱。
【输入格式】
输入包含三行。
第一行为N（不大于12的正整数）。
第二行有三个数，A，K，B（J均不大于100）。
第三行为每个月需要的最少人数（均小于1000）。
【输出格式】
输出包括一个数字即最小费用。
【样例输入】
3
456
10911
【样例输出】
199
考虑每一个月，比较当前的工人数M1和下一个月所需要的工人数M2，若M1≤M2，则必须雇佣缺少的工人，当然也不会多雇。
问题的关键就在于可以解雇的时候解雇多少工人，可以认为对于一组给定的A,K和B就可以得到一个吃大锅饭的最长时间（超过该时间可以解雇了后再雇佣），这样我们找到这个时间内的最大工人需求量M3，若M1≤M3，那么不用解雇任何工人，否则就要解雇M1-M3个工人。
需要注意的是，判断最长时间时需要考虑到期的时候不付精神损失费的特殊情况。
而采用动态规划则要简单得多。
设F[I,J]表示完成了前I个月的工作任务且第I个月有J个工人所需的最小费用，则有F[I,J]=Min{F[I-1,H]+G（H,J）+K*J}，其中G（H,J）表示由H个工人变化到J个工人所要支付的费用（或雇佣或解雇）。
使用动态规划来解决这道题目，无论从思路还是实现来说都要比贪心算法简单。
在有规定时间限制的竞赛中，做题的速度也很重要。
这催生了我们使用动态规划的第二个动机——解决复杂的分步讨论的贪心决策问题。
但仅限于数据范围不大的情况，因为较比贪心算法，动态规划的时间复杂度要大一些。
总地来说，这类动态规划牺牲了程序的时空效率，但思维和编程比较简单，可以节约宝贵的竞赛时间。
2.动态规划的状态划分方法
在这里我们把动态规划状态的划分方法分为3种：
一维状态划分、二维状态划分和树型状态划分。
树型动态规划是由于树这种数据结构的特殊性衍生出来的（放在最后说），这里先讨论一下一维状态划分和二维状态划分的动态规划。
前面提到的动态规划基本都属于一维状态划分，以NumberTriangles的方程为例（F[I,J]表示从顶层走到第I行第J列的点能取得的最大和）。
定义I为阶段变量，J为状态变量（我为了自圆其说，方便讲解，自己定义的），阶段变量可以确定状态所在阶段，而状态变量则反映状态本身的性质。
允许只有阶段变量没有状态变量，例如HurdlesRace里的F[I]。
而前面提到的二维状态划分只有Skiing一题（F[I,J]表示滑到第I行第J列的点时存在的最长滑坡长度），因为这里I和J两个变量才能确定状态所在的阶段。
2.1.1典型的线性动态规划
我们通常说的线性动态规划就是一维状态划分的没有状态变量的动态规划。
下面了列举几个典型的线性动态规划题图：
UVA10684TheJackpot
【题目描述】
某人想迅速变得富有，但是他还不想工作。
于是他开始赌博，存在一个奖金序列（有正有负），他想从中赢得最多的钱，我们规定他中途只可以退出一次（退出后不可以再回来）。
【输入格式】
输入第一行包含一个正整数N（N≤10000），接下里包含N个整数，它们的绝对值都不超过1000。
【输出格式】
输出该人能赢得的最大钱数。
【样例输入】
5
12-4-1049
【样例输出】
13
我们称该类问题为最大连续数字和。
设F[I]表示到I为止（必须含A[I]）的最大连续整数和，如果F[I-1]为负数，那么显然F[I]=A[I]，否则有F[I]=F[I-1]+A[I]。
这样就构造出一个线性动态规划算法了，以下是它的一个经典应用：
NECPC2007SumOfSubRectangularParallelepiped
【题目描述】
现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。
每个单位立方体都有一个整数值。
现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。
【输入格式】
第一行包含一个整数n。
接下来n个n2的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值。
【输出格式】
输出仅包括最大的长方体的数和。
【样例输入】
2
12
21
-1–2
-2-1
【样例输出】
6
最基础的方法是“直译”枚举过程，时间复杂度O（n9）。
而记录先前考察的结果。
如图所示，在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。
经过这样的优化，利用了前面的计算结果，时间复杂度降为O（n8）。
而对于每个平面的矩形有一种经典的压缩方法，设rec[x,y,z]表示z轴坐标为z的水平面中矩形（1,1,x,y）的数和。
则z轴坐标为z的水平面中左上角为（x1,y1）、右下角为（x2,y2）的矩阵的数和为rec[x2,y2,z]+rec[x1,y1,z]-rec[x2,y1,z]-rec[x1,y2,z]。
有了上面的关系式，我们下面要做的只是枚举z,x1,x2,y1,y2来查找最优解。
对于每组固定的x1,x2,y1,y2，rec[z,x1,x2,y1,y2]就等于z个数字，那么只要求它们的最大连续和就可以。
总的时间复杂度为O（n5）。
Noip2004合唱队型
【题目描述】
N位同学站成一排，音乐老师要请其中的（N-K）位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：
设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...Ti+1>…>TK（1≤i≤K）。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入格式】
第一行是一个整数N（2≤N≤106），表示同学的总数。
第一行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。
【输出格式】
只包含一个整数，就是最少需要几位同学出列。
【样例输入】
8
186186150200160130197220
【样例输出】
4
首先只考虑左半部分的合唱队型，这种题目类型叫做最长上升子序列问题（LIS），最常规的算法是设F[I]表示前I个数字中（必须包含A[I]）的最长上升子序列的长度，状态转移方程为F[I]=Max{F[J]+1}，其中J∈[0,I-1]且A[J]I和J都需要枚举，所以时间复杂度为O（n2）。
实际上LIS有一种贪心算法，我们用数组G[I]记录当前长度为I的上升子序列的最后一个元素的最小值，那么G[I]将会是一个单调的序列。
对于每一个A[J]，只要在G序列中找到一个最大的I，使得G[I]
升级会员 