2.7　动态规划初步

本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第9章。

习题9-1　最长的滑雪路径（Longest Run on a Snowboard，UVa 10285）

在一个R*C（R，C≤100）的整数矩阵上找一条高度严格递减的最长路。起点任意，但每次只能沿着上下左右4个方向之一走一格，并且不能走出矩阵外。如图2.51所示，最长路就是按照高度25、24、23、…、2、1这样走，长度为25。矩阵中的数均为0～100。

【分析】

用D［i，j］来表示从［i，j］开始能走的高度严格递减的最长路，则很容易发现D［i，j］的状态转移方程：D［i，j］＝max（1＋D［i1，j1］），其中（i1，j1）是比［i，j］高度小的4个相邻的格子之一。边界条件是当没有符合条件的i1和j1时，D［i，j］＝1。使用记忆化搜索即可，时间复杂度是O（R*C）。

习题9-2　免费糖果（Free Candies，UVa10118）

桌上有4堆糖果，每堆有N（N≤40）颗。佳佳有一个最多可以装5颗糖的小篮子。他每次选择一堆糖果，把最顶上的一颗拿到篮子里。如果篮子里有两颗颜色相同的糖果，佳佳就把它们从篮子里拿出来放到自己的口袋里。如果篮子满了而里面又没有相同颜色的糖果，游戏结束，口袋里的糖果就归他了。当然，如果佳佳足够聪明，他有可能把堆里的所有糖果都拿走。为了拿到尽量多的糖果，佳佳该怎么做呢？

【分析】

初步看，状态包含4堆糖果的高度hs［4］以及当前篮子内是否有各色糖果。如果全部考虑进去，空间复杂度会大到无法接受。思考之后会发现，只要有两个相同的糖果就会被拿出来，对于特定的hs，篮子中的状态就可以确定。

可以对hs［4］进行回溯搜索，每一步尝试从一堆糖果顶端取出一个糖果。同时记忆hs对应的状态，减少重复计算。算法的时间和空间复杂度都刚好是O（n⁴）。完整程序如下：

习题9-3　切蛋糕（Cake Slicing，ACM/ICPC Nanjing 2007，UVa1629）

有一个n行m列（1≤n，m≤20）的网格蛋糕上有一些樱桃。每次可以用一刀沿着网格线把蛋糕切成两块，并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃，且切割线总长度最小。如图2.52所示是一种切割方法。

【分析】

有一个明显的递归子结构，就是包含1个以上樱桃的子矩形r、c、w、h。左上角[r,c]，宽为w、高为h。

记D(r,c,w,h)（下文简称d）为这个矩形的最小切割线长度，对于这个矩形来说，只有横竖两种切法：

（1）遍历所有合法的横切，d=min(d, min(w+D(r+i, c, w, h-i)+D (r, c, w, i))), i∈[1,h]。

（2）遍历所有合法的竖切，d=min(d, min(h+D(r,c,i,h)+D (r, c+i, w-i, h))), i∈ [1,w]。

边界条件是(r,c,w,h)对应的子矩形中刚好只有1个樱桃，此时d=0。遍历时需要保证切开的两个矩形都至少包含1个樱桃。

在遍历过程中需要求出每个子矩形的樱桃个数，可以用求D类似的递归结构来记忆化搜索所有子矩形的樱桃个数。算法的时空复杂度都是O(n³m³)。完整程序（C++11）如下：

习题9-4　串折叠（Folding, ACM/ICPC NEERC 2001, UVa1630）

给一个由大写字母组成的长度为n（1≤n≤100）的串，“折叠”成一个尽量短的串。例如AAAAAAAAAABABABCCD折叠成9（A）3（AB）CCD。折叠是可以嵌套的，例如NEERCYESYESYESNEERCYESYESYES可以折叠成2（NEERC3（YES））。多解时可以输出任意解。

【分析】

参考“最优矩阵链乘”问题的思路，进行区间规划。记输入串为S，DP（L，R）表示这个区间的最优折叠结果的字符串表示，用STL的string来存储。则状态转移方程如下：

（1）边界条件：L＝R时，DP（L，R）＝“S［L］“。

（2）L＜R，则考虑两种策略，取长度最短的方案：

• □　把区间切分成两部分，分别折叠然后拼接，遍历所有的区间切分方案［L，k］和［k＋1，R］（L≤k＜R），求出令DP（L，k）和DP（k＋1，R）长度之和最小的k值kMin，则有DP（L，R）＝DP（L，kMin）＋DP（kMin＋1，R）。
• □　如果S［L，R］是周期串，首先求出最小的重复串长度cycle（0＜cycle≤（L-R＋1）／2），记rep＝（L-R＋1）／cycle，也就是重复次数。这样把区间变成DP（L，L＋cycle-1）的rep次折叠。DP（L，R）＝“cnt（“＋“DP［L］［L＋cycle-1］“＋“）“。例如，“ABABABAB”变成“4（AB）”。

所求结果就是DP（0，n-1），算法的时间空间复杂度均为O（n³）。完整程序如下：

习题9-5　邮票和信封（Stamps and Envelope Size, ACM/ICPC World Finals 1995, UVa242）

假定一张信封最多贴5张邮票，如果只能贴1分和3分的邮票，可以组成面值1～13以及15，但不能组成面值14。我们说：对于邮票组合{1,3}以及数量上限S=5，最大连续邮资为13。1～13和15的组成方法如表2.1所示。

输入S（S≤10）和若干邮票组合（邮票面值不超过100），选出最大连续邮资最大的一个组合。如果有多个并列，邮票组合中邮票的张数应最多。如果还有并列，邮票从大到小排序后字典序应最小。

【分析】

对于邮票组合C，令DP[i]表示邮资i至少需要多少张来自于C的邮票才能组合起来。则DP[i]=min(DP[i-x]+1, x∈C且x≤i)。则对于C来说最大连续邮资就是第一个符合DP[i+1]>S的i。这样就可以求出每个组合的最大连续邮资。时间和空间复杂度都为O(100*maxS)。完整程序（C++11）如下：

习题9-6　电子人的基因（Cyborg Genes, UVa10723）

输入两个A～Z组成的字符串（长度均不超过30），找一个最短的串，使得输入的两个串均是它的子序列（不一定连续出现）。你的程序还应统计长度最短的串的个数。如ABAAXGF和AABXFGA的最优解之一为AABAAXGFGA，一共有9个解。

【分析】

参考LCS问题的思路。记输入的两个字符串为S1和S2，定义pa(i,j)为S1[1…i]和S2[1…j]的公共父串的最短长度。则pa的状态转移方程如下：

（1）pa(i,j)=min(pa(i-1,j)+1,pa(i,j-1)+1)，其中S1[i]≠S2[j]，对应父串的最后一位是使用S1[i]还是S2[j]。

（2）pa(i,j)=pa(i-1,j-1)+1，其中S1[i]=S2[j]，则父串的最后一位是确定的。

（3）边界条件是：当i=0或者j=0时，pa(i,j)=max(i,j)，则父串一定是S1[1…i]和S2[1…j]其中之一。

然后求最短父串的方案个数：定义pac(i,j)为S1[1…i] and S2[1…j]的最短公共父串的个数。S1[i]=S2[j]时，pac(i,j)=pac(i-1,j-1)，因为父串的最后一位只有1种选择。否则记p1=pa(i-1, j)，p2=pa(i, j-1) ，则有：

• □　pac(i,j)=pac(i-1, j)+pac(i, j-1)，此时p1=p2，表示父串最后一位可以使用S1[i]和S2[j]两种方案。
• □　pac(i,j)=pac(i-1, j), p1 < p2，父串必须使用S1[i]才能保证最短。
• □　pac(i,j)=pac(i, j-1), p1 > p2，父串必须使用S2[j]才能保证最短。
• □　边界条件是：当i=0或者j=0时，pac(i, j)=1，父串只有1种选择。

时间复杂度和空间复杂度都为O(|S1|*|S2|)。注意，输入的S1和S2长度可能是0，输入时要用gets或者STL里面的getline而不能用scanf。完整程序如下：

习题9-8　阿里巴巴（Alibaba, ACM/ICPC SEERC 2004, UVa1632）

直线上有n（n≤10000）个点，其中第i个点的坐标是x_i，且它会在d_i秒之后消失。Alibaba可以从任意位置出发，求访问完所有点的最短时间。无解输出No solution。

【分析】

最优的访问策略是在任意时刻，访问过的点要形成一个连续区间，中间不存在未访问过的点（顺路都可以把那个点访问了）。

定义：

• □　D（i，j，0）：访问i到j，最后停在i点所需要的最少时间。
• □　D（i，j，1）：访问i到j，最后停在j点所需要的最少时间。

则状态转移方程如下：

• □　D（i，j，0）＝min（D（i＋1，j，0）＋x_i＋1-x_i，D（i＋1，j，1）＋x_j-x_i），其中有两种策略：先访问i＋1到j，停在i＋1再去i，或者停在j再去i。
• □　D（i，j，1）＝min（D（i，j-1，1）＋x_j-x_j-1，D（i，j-1，0）＋x_j-x_i），其中有两种策略：先拿i到j-1的物品，停在j-1再去拿j，或者停在i再去拿j。

时间和空间复杂度都为O（2*n²）。需要注意的是，题目没有明确说，但是可以假设Alibaba单位时间移动一个单位的距离。

习题9-9　仓库守卫（Storage Keepers，UVa10163）

你有n（n≤100）个相同的仓库。有m（m≤30）个人应聘守卫，第i个应聘者的能力值为P_i（1≤P_i≤1000）。每个仓库只能有一个守卫，但一个守卫可以看守多个仓库。如果应聘者i看守k个仓库，则每个仓库的安全系数为P_i/K的整数部分。没人看守的仓库安全系数为0。

你的任务是招聘一些守卫，使得所有仓库的最小安全系数最大，在此前提下守卫的能力值总和（这个值等于你所需支付的工资总和）应最小。

【分析】

类似于背包问题，令F（i，j）表示前i个人，管理j个仓库的最小安全系数最大值，则有：

• □　F（i，0）＝INF，0个仓库最小安全系数可以认为是INF，方便递推。
• □　F（1，j）＝P₁/j，每个仓库的安全系数都是P₁/j。
• □　记k为第i个人管理的仓库个数（0≤k≤j），G（k）为第i个人管理k个仓库时，前j个仓库最小安全系数的最大值。则k＝0时，G（0）＝F（i-1，j），否则G（k）＝min（F（i-1，j-k），P_i/k)。F(i,j)=max(G(k))。

记mx＝F（m，n），然后就是求工资总和：G（i，j）表示前i个人，管理j个仓库的达到最大安全系数前提下，这i个人能力总和的最小值。

• □　G（i，0）＝0，0个仓库只需要0个人管。
• □　G（1，j）＝P_i/j≥mx？P_i：INF，只能选择让安全系数超过最大值的人来管理这G个仓库。
• □　G（i，j）＝min（G（i-1，j-k）＋P_i），其中P_i/k≥mx & 0≤k≤j，这里依然是对第i个人管理的仓库个数k进行决策。

需要注意的是，上述状态转移过程中，如果k＝0，则有P_i/k＝INF。空间复杂度为O（n*m），时间复杂度为O（n²*m）。完整程序（C＋＋11）如下：

习题9-10　照亮体育馆（Barisal Stadium, UVa10641）

输入一个凸n（3≤n≤30）边形体育馆和多边形外的m（1≤m≤1000）个点光源，每个点光源都有一个费用值。选择一组点光源，照亮整个多边形，使得费用值总和尽量小。如图2.53所示，多边形ABCDEF可以被两组光源{1,2,3}和{4,5,6}照亮。光源的费用决定了哪组解更优。

【分析】

照亮整个多边形，也就是要选择一组费用最小的光源，使得每个顶点都被照亮。首先需要计算出每个光源可以照到哪些顶点。例如，图2.53中光源1可以照亮边AB（包含A、B两个顶点），一定存在多边形内部的一个点，刚好和点1分别位于AB的不同侧。进一步，先通过把所有顶点坐标求平均值得到一个多边形内部的点O，再使用叉积来计算每个光源可以照亮的边和顶点。

而本题中所有顶点形成一个环，不难想到首先要把环变成直线，可以把区间[0,n)扩大两倍成为[0,2n)，其中i≥n对应原来的点i-n，然后再预处理出每个光源能够照亮的顶点编号区间[L,R]。一组光源只要能把[0,2n)的任意一个包含n个顶点的子区间内的所有顶点都照亮，就是一组符合要求的解。现在就是要求出所有解中费用最小的。

对于顶点i（0≤i<n）：定义D(j)为顶点编号区间[i, j)内的顶点都被照射到所需的最小费用，则本题的解就是min(D(i+n)), 0≤i<n。对于每个i，从小到大遍历顶点编号j（i≤j<i+n），然后考虑每个能照射到j的光源lt，记r=min(lt.R,i+n)，表示使用了lt之后，能够照射到的右边界。分是否使用lt两种情况考虑进行状态转移，用D(j)更新D(r)：D(r)=min(D(r),D(j)+lt.c)，其中lt.c表示光源lt的费用。

时间复杂度为O(2n²m)，空间复杂度为O(n)。完整程序如下：

习题9-11　禁止的回文子串（Dyslexic Gollum, ACM/ICPC Amritapuri 2012, UVa1633）

输入正整数n和k（1≤n≤400，1≤k≤10），求长度为n的01串中有多少个不含长度至少为k的回文连续子串。例如n=k=3时只有4个串满足条件：001, 011, 100, 110。

【分析】

首先，长度为a+2的回文，去掉两端字符之后一定是长度为a的回文。也就是说，只要保证不包含长度为k和k+1的回文串，则一定不包含更长的回文串。

题目中k比较小（k≤10），可以把长度为k的串作为一个整体，使用一个整数来记录（≤1024），这样可以直接使用位运算。否则用字符串记录，还需要做时间复杂度高得多的字符串运算。

令F(i,b)表示已经确定了从左到右的前i位，其中最右边k位对应的整数为b，剩下的n-i位上所有方案的个数。

首先引入以下变量：

（1）b₀=(b<<1)，表示b左移一位，然后右边补0，得到的k+1位串。

（2）b₁=(b<<1)+1，表示b左移一位，然后右边补1，得到的k+1位串。

（3）c₀=b₀& ((1<<k)-1)，表示取b₀最右边k位得到的k位串。

（4）c₁=b₁& ((1<<k)-1)，表示取b₁最右边k位得到的k位串。

c₀和c₁分别表示确定了第i+1位之后的最右边k位串，分别对应第i+1位为0和1两种情况，则状态转移方程如下：F(i, b)=F(i+1,c₀)+F(i+1,c₁)。上述方程中，要求b₀、b₁、c₀、c₁不是回文，并且其最右边k位也不是回文。

边界条件是当i=n时F=1。则最终答案就是ΣF(k,b),其中b是所有k位的非回文。算法的时间和空间复杂度均为O(n*2^k)。

完整程序如下：

习题9-12　保卫Zonk（Protecting Zonk, ACM/ICPC Dhaka 2006, UVa12093）

给出一个n（n≤10000）个结点的无根树。有两种装置A和B，每种都有无限多个。

（1）在某个结点X使用A装置需要C1（C1≤1000）的花费，并且此时与结点X相连的边都被覆盖。

（2）在某个结点X使用B装置需要C2（C2≤1000）的花费，并且此时与结点X相连的边以及与结点X相连的点、相连的边都被覆盖。

求覆盖所有边的最小花费。

【分析】

不难想到是树形DP，考虑每个结点的覆盖状态。不妨把n=1作为树根。令D(u,s)表示以结点u为根的子树，当前覆盖状态为s，所需的最小花费。对于结点u，统称其任意孩子为v，任意孙子为vx，u的父亲为p，p的父亲为px，u的任意兄弟结点统称为ux。s分以下4种情况（参考图2.54，虚线表示未覆盖，实线已经覆盖s）：

（1）s=0：边u-v，v-vx，u-p，p-px全部覆盖。

（2）s=1：边u-v，v-vx，u-p全部覆盖。

（3）s=2：边u-v，v-vx全部覆盖。

（4）s=3：u-v，还有部分未覆盖。

则所求答案为min(D(1,0),D(1,1),D(1,2))。从叶子到根结点从下往上每次一层进行决策，则这个过程可以写成dfs，状态转移的前提是u的孙子结点对应的子树已经全部覆盖。则状态转移过程如下：

（1）s=0：这种状态一定要求u上放置一个B，v的状态转移方程式：D(u,0)= min(D(v,0),D(v,1),D(v,2),D(v,3)))。

（2）s=1：则要求v的覆盖状态≠3。要转移到u的这种状态有两种可能：u上放一个A，或者且至少有一个v的覆盖状态=0。记w=(min(D(v,0),D(v,1),D(v,2)))，则D(u,1)=min((C1+w),w–min(D(v,0)–min(D(v,0),D(v,1),D(v,2)))。

（3）s=2：要转移到这个状态，就要求所有v的覆盖状态为1。D(u,2)= D(v,1)。

（4）s=3：则v的状态可以是0、1、2其中之一。D(u,3)=w。

dfs中的循环次数刚好是所有的结点次数，所以算法的时间复杂度为O(n)。完整程序（C++11）如下：

习题9-14　圆和多边形（Telescope, ACM/ICPC Tsukuba 2000, UVa1543）

给出一个圆和圆周上的n（3≤n≤40）个不同点，请选择其中的m（3≤m≤n）个点，按照在圆周上的顺序连成一个m边形，使得它的面积最大。例如在如图2.55所示的例子中，右上方的多边形最大。

【分析】

假设总共有n个点。记D(i,j,k)为在第i～j个点中选择k个点（其中必须包含i和j，0≤i<i+1<j<n），所能组成的最大的多边形面积。对选择的k个点中j之前的最后一个点x（i<x<j）进行决策，则有D(i,j,k)=max(D(i,x,k-1)+area(i,x,j))，如图2.56所示。其中，area(i,x,j)为i、x、j这3个点组成的三角形面积。所求结果为max(D(0,n,m))。算法的时间复杂度为O(n³)。

需要注意的是，需要预先把任意3个点组成的三角形面积计算出来，以便在递推D时使用。完整程序如下：

习题9-15　学习向量（Learning Vector, ACM/ICPC Dhaka 2012, UVa12589）

输入n个向量（x,y）（0≤x,y≤50)，要求选出k个，从(0,0)开始画，使得画出来的折线与x轴围成的图形面积最大。例如4个向量是(3,5)、(0,2)、(2,2)、(3,0)，可以依次画(2,2)、 (3,0)、(3,5)，围成的面积是21.5，如图2.57所示。输出最大面积的两倍。1≤k≤n≤50。

【分析】

如果画出来的折线形成凹多边形，调整成凸多边形一定面积更大（如图2.58所示），所以任何最优选择中的k个向量一定是按照斜率从大到小依次选择的。对所有向量按照斜率从大到小进行排序。考虑x可能为0，向量的斜率可以使用函数atan2(y, x)计算。

记F(i,c,h)为还要在i个向量中，还要选择c个，画出折线的最高y坐标为h。后续还能再增加的最大面积（如图2.59的浅色部分所示）。

状态转移方程：F(i,c,y)=max(F(i+1, c, y), F(i+1, c+1, y+v.y)+(2*y+v.y)*v.x)，其中v为第i个向量，有是否使用向量v的两种决策。边界条件为i=n,c=k时，F=0。所求结果为F(0,0,0)。算法的时间复杂度为O(50*n³)。

习题9-18　棒球投手（Pitcher Rotation, ACM/ICPC Kaosiung 2006, UVa1379）

你经营着一支棒球队。在接下来的g+10天中会有g（3≤g≤200）场比赛，其中每天最多一场比赛。你已经分析出你的n（5≤n≤100）个投手中每个人对阵所有m（3≤m≤100）个对手的胜率（一个n*m矩阵），要求给出作战计划（即每天使用哪个投手），使得总获胜场数的期望值最大。需要注意的是，一个投手在上场一次后至少要休息4天。

【分析】

每个投手上场一次至少休息4天，对于每场比赛来说，胜率最高的5个投手不可能前面4天都参加比赛（每天最多一场，每场只需1个投手），所以至少有1个休息够了，可以只考虑胜率最高的5个人。

令DP(i,p0,p1,p2,p3)表示第i天，选择对阵当天对手胜率排名第p0的对手上场，且第i-x天选择对应排名第px的上场，前i天所能得到的最大得分。其中px=0则表示当天无人上场。

状态转移时，首先要保证第i天选择的对手不能和前面4天重复，然后对于每i天来说，有两种情况：

（1）没有比赛：则D(i,0,p1,p2,p3)=max(D(i-1,p1,p2,p3,p4)，其中0≤p4≤5。

（2）有比赛：则D(i,p0,p1,p2,p3)=max(D(i-1,p1,p2,p3,p4)+p)，对p0进行决策，p是对当天对手胜率排名p0的选手的胜率。

时间复杂度为O(g*5⁵⁾，因为五维数组占用空间较大，需使用滚动数组，这样空间复杂度就是常数O(2*6⁴)。完整程序如下：