信息学竞赛中的动态规划专题
哈尔滨工业大学周谷越
【关键字】
动态规划动机状态典型题目辅助方法优化方法
【摘要】
本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。
【目录】
1.动态规划的动机和基本思想
1.1.解决重复子问题
1.2.解决复杂贪心问题
2.动态规划状态的划分方法
2.1.一维状态划分
2.2.二维状态划分
2.3.树型状态划分
3.动态规划的辅助与优化方法
3.1.常见辅助方法
3.2.常见优化方法
4.近年来Noi动态规划题目分析
4.1 Noi2005瑰丽华尔兹
4.2 Noi2005聪聪与可可
4.3 Noi2006网络收费
4.4 Noi2006千年虫
附录参考书籍与相关材料
1.动态规划的动机和基本思想
首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。
1.1 解决重复子问题
对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题：
USACO 1.4.3 Number Triangles
http://122.139.62.222/problem.php?id=1417
【题目描述】
考虑在下面被显示的数字金字塔。
写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 1
在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。
【输入格式】
第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。
【输出格式】
单独的一行包含那个可能得到的最大的和。
【样例输入】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 1
【样例输出】
30
显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层
的两个4走来，假设分别知道走到次底层的两个4的最优解，那么取其中较大的加上6就是走到最底层的6时的最优解。然而次底层的两个4还可以走向最底层的2和1，这样就产生了重复的子问题。动态规划的第一类动机就是为了要避免这种重复运算。
事实上，子问题的个数是确定的，只要我们能够把已经计算过的子问题记录下来，再下次需要时直接使用，便可以大大提高程序的效率。
下面介绍一下动态规划的相关概念。首先动态规划是来解决最优化问题的，再进一步说就是解决最优化问题中的多阶段决策问题。
以下是动态的定义内容，在各种基础书籍上都有相关讲解，在此仅列出，不做累述。
状态（State）：表示事物的性质，是描述动态规划中的单元的量。
阶段（Stage）：阶段是一些性质相近的状态集合。
决策（Decision）：每个阶段做出的某种选择性行动，是程序所需要完成的选择。
状态转移方程（Equal）：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是动态规划的核心。
初始状态：由已知能够确定的状态。
目标状态：表示解或能够转化为解的状态。
总体看来，由初始状态经过若干阶段通过若干决策推出目标状态的过程就是动态规划。下面我们就Number Triangles一题对这些概念对号入座：
首先确定状态，用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]
For I = 2 to N Do
For J = 1 to I Do
If F[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/ICPC Shanghai2001 Skiing
http://122.139.62.222/problem.php?id=1862
【题目描述】
滑雪是一项很受欢迎的体育运动，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡。我们想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
我们可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
【输入格式】
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 500)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
【输出格式】
输出最长区域的长度。
【样例输入】
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
【样例输出】
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值，下面同样给出程序主干部分：
Function F (Int I, Int J)
{
If Arr[I,J] > 0 Then
Return Arr[I,J]
Int P, Ans = 0
For P = 1 to 4 Do
If ((I+DX[P],J+DY[P]) In Map) And (H[I+DX[P],J+DY[P]] > H[I,J]) Then
If (Ans < F[I+DX[P],J+DY[P]])
Ans = F[I+DX[P],J+DY[P]]
Arr[I,J] = Ans + 1
Return Arr[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组成的状态，从贪心的角度看，它们就是多余的，就是为了使用动态规划扩展出来的状态。当然，就这道题目来看，贪心算法无论是从