动态规划方法例题

1、动态规划方法例题最长上升子序列问题 一个序列有N个数：A1,A2,AN，求出最长上升子序列的长度（LIS：longest increasing subsequence)。 例如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 5, 9) , (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 9) ，(1, 3, 5, 8)和(1, 3, 4, 8). 分析 假如我们考虑求A1,A2,Ai的最长上升子序列的长度，其中iN，那么上面的问题变成了原问题的一个子问题(问题规模变小了，可让i=1,2,3等来分析) 然后我

2、们定义d(i)，表示前i个数中以Ai结尾的最长上升子序列的长度。这个d(i)就是我们要找的状态。 如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。状态找到了，下一步来找状态转移方程。 找出状态转移方程我们来看下面这6个数的序列：5，3，4，8，6，7我们可以得到：（下文的最长上升子序列都用LIS表示）前1个数的LIS长度d(1)=1(序列：5) 前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的) 前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3) 第1阶段决策选优：求最长最长上升子序列的长度 需要判断当前的数是否与其左边最长

3、左边最长上升子序列构成一个上升序列，如果是，则： d(3)= maxd(1),d(2)+1； 即第3个数左边最长上升子序列最大长度+1 前4个数的LIS长度d(4)=3 (序列：3，4，8；8前面比它小的有3个数，所以 d(4)=maxd(1),d(2),d(3)+1=3状态转移方程如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：d(i) = maxd(j)+1 （1）其中j=1,2, . ,i-1, AjAi有可能i前面的各个子序列中最后一个数都大于Ai，那么d(i)=1 （2）即它自身成为一个长度为1的子序列。求解LIS的C+代码段int len = 1

4、; for(int i=0; in; +i) di = 1;/数组d用来保存子序列的长度 for(int j=0; ji; +j) if(Ajdi) di = dj + 1; if(dilen) len = di; 序列变化 求最长非降子序列(longest non-decreasing subsequence)，与此问题近似。只需要将上述条件AjAi改为：AjAi。 求最长下降子序列(longest decreasing subsequence)，将上述条件AjAi。 如果要求最长非递增子序列（longest non-increasing subsequence），将上述条件AjAi改为：A

5、jAi。 蓝桥杯网站练习系统算法训练中的“拦截导弹拦截导弹”问题，本质上就是一个求最长非递增子序列长度的题。 例1 拦截导弹 某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 （蓝桥网编号：ALGO-13 VIP试题 ）拦截导弹输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。输入第一行

6、输入测试数据组数N（1=N=10）接下来一行输入这组测试数据共有多少个导弹m（1=m=20）接下来行输入导弹依次飞来的高度，所有高度值均是大于10的正整数。输出输出最多能拦截的导弹数目 拦截导弹 样例输入输出 样例输入 SAMPLE INPUT:28389 207 155 300 299 170 158 65388 34 65SAMPLE OUTPUT:6389 300 299 170 158 65 分析 因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的导弹高度组成一个非递增序列。 题目要求我们计算

7、这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要在导弹依次飞来的高度序列中寻找一个最长非递增子序列的长度一个最长非递增子序列的长度。状态转移方程如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：d(i) = maxd(j)+1 （1）其中j=1,2, . ,i-1, Aj Ai有可能i前面的各个子序列中最后一个数都小于Ai，那么d(i)=1 （2）即它自身成为一个长度为1的子序列。只需修改这个符号，就可以求最长非递增子序列求解拦截导弹问题的C+代码段int len = 1; for(int i=0; in; +i) di = 1;/数组d用

8、来保存子序列的长度 for(int j=0; j=Ai & dj+1di) di = dj + 1; if(dilen) len = di; 例例2 乘积最大乘积最大 问题描述 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法： 1）3*12=36 2）31*2=62 这时，符合题目要求的结果是： 31*2=62 现在，请你设计一个程序，求得正确的答案。（蓝桥网站题目编号：ALGO-17 VIP试题2013-11-07 ）输入输出样例输入： 输入中有若干

9、组测试数据，每组测试数据有两行：第一行共有2个自然数T，K （6=T=40，1=K=6），第二行是一个长度为T的数字串。输出: 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。输入样例: 4 21231 输出样例：62分析：划分阶段假设在n0n1ni(2in)中插入k个*。其中n0n1nt中插入了k-1个*，即乘式中的第k+1项为nt+1ni(kti-1) ，即有形式： itktnnnn1*10* 个插入状态转移方程设Fik是长度为i+1的数串 中插入k个“*”的最大乘积（整型数组），0ki。ittnnnn10.1* 1max10itnumktFkiFtkittnnnn10

10、.显然显然Fi0= ，i=0，1，2，N-1；状态转移方程为状态转移方程为 高精度运算由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，需要采用高精度运算，这里仅介绍解题思路。 为了便于大家理解算法思想，程序中只是用了在长整型范围内的数据处理，如整数的分划、合成和乘法运算等。 01背包问题 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为P1,P2,.,Pn.若每种物品只有一件只有一件，求旅行者能获得最大总价值。 输入输出 输入格式：M,NW1,P1W2,P

11、2.输出格式： X 分析 阶段：在前i件物品中，选取若干件物品放入背包中； 状态：在前i件物品中，选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值； 决策：第i件物品放或者不放； 状态转移方程 可以按每个物品划分阶段； 每种物品有选和不选两种选择（决策） 设F(i,j)表示前i件物品载重为j的最大效益，则有 1=i=N, 0=j=wi then /背包容量够大 fi,j:=max(fi-1,j-wi+pi,fi-1,j)else /背包容量不足 fi,j:=fi-1,j;end;例3 入学考试 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为

12、师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自采每一株都需要一些时间，每一株也有它自身的价值身的价值。我会给你一段时间会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？ 蓝桥网编号：ALGO-30 VIP试题 2013-11-08输入输出格式输入格式第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采

13、药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 输入输出样例样例输入70 371 10069 11 2样例输出3数据规模和约定对于30%的数据，M = 10；对于全部的数据，M = 100。 分析 这是一个典型的01背包问题 可以将T（总共能够用来采药的时间）看作背包容量 将采每一株草药需要时间的时间看作物品重量 将每株草药的价值看作物品的价值例4 开心的金明 金明今天很开心，家里购置的新房就要领钥匙了，新房

14、里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1.jk，则所求的总和为：vj1*wj1+.+vjk*wjk请你帮助金明设计一个满足要求的购物单。 蓝桥

15、网题目编号：ALGO-31 VIP试题 2013-11-08 输入输出【输入文件】输入的第1行，为两个正整数，用一个空格隔开：N m（其中N（30000）表示总钱数，m(25)为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格（v10000），p表示该物品的重要度（15）【输出文件】输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（=wi),fi-1,j 主要程序段for(i=0;in;i+)f0i=0;/初始化最大价值数组的第0行；for(i=1;im;i+)for(j=0;j=vi

16、)&(fi-1j-vi+vi*pifij) fij=fi-1j-vi+vi*pi;/*如果当前物品的价格小于总价格(j=vi)*/ 例5 装箱问题有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入格式第一行为一个整数，表示箱子容量；第二行为一个整数，表示有n个物品；接下来n行，每行一个整数表示这n个物品的各自体积。输出格式一个整数，表示箱子剩余空间。蓝桥网编号：ALGO-21 VIP试题 2013-11-07 输入输出样例样例输入2468312797样例输出0分析这是一

17、个变形的背包问题，最优目标是：使箱子的剩余空间为最小。可转换成物品占据的容量最大。 用Fi,j表示容量为j的箱子装入前i个物品后，物品占据的容量。则状态转移方程为：Fi,j= maxFi-1,j-ai+ai，Fi-1,j其中ai表示第i个物品的体积。 主要代码段dp0=0;/注意这是关键 for(i=0;i=a;j-) dpj=max(dpj,dpj-a+a); 收集苹果：二维的DP问题 平面上有NM个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。 我们必须注意到的一点是，到

18、达一个格子的方式最多只有两种：从左边来的(除了第一列)和从上边来的(除了第一行)。分析 因此为了求出到达当前格子后最多能收集到多少个苹果，我们就要先去考察那些能到达当前这个格子(i,j)之前的格子，到达它们最多能收集到多少个苹果。(i-1,j)(i,j-1)(i,j)Ai,j状态和状态转移方程状态Sij表示我们走到(i, j)这个格子时，最多能收集到多少个苹果。那么，状态转移方程如下：Sij=Aij + max(Si-1j, if i0 ; Sij-1, if j0)其中i代表行，j代表列，下标均从0开始；Aij代表格子(i, j)处的苹果数量。例6 传纸条 小渊和小轩是好朋友也是同班同学，他

19、们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事

20、情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。蓝桥网题目编号：ALGO-36VIP试题2013-11-08输入输出格式输入格式输入第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1=m,n=50）。接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。输

21、出格式输出一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。样例输入输出样例输入3 30 3 92 8 55 7 0样例输出34数据规模和约定30%的数据满足：1=m,n=10100%的数据满足：1=m,n=50 传纸条传纸条(甩干后甩干后) 小渊坐在矩阵的左上角，坐标小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩，小轩坐在矩阵的右下角，坐标阵的右下角，坐标(m,n)。从小渊传到小轩的纸条。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。条只可以向上或者向左传递。 班里每个同学都可以

22、帮他们传递，但只会帮他们班里每个同学都可以帮他们传递，但只会帮他们一次。一次。 每个同学愿意帮忙的好感度有高有低，可以用一每个同学愿意帮忙的好感度有高有低，可以用一个个0-100的自然数来表示，数越大表示越好心。的自然数来表示，数越大表示越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度条路径上同学的好心程度之之和最大。现在，请你和最大。现在，请你帮助小渊和小轩找到这样的两条路径。帮助小渊和小轩找到这样的两条路径。 1=m,n=50贪心 很容易想到一个算法：很容易想到一个算法： 求出求出1个纸条从（个纸条从（1，1）到（）到（M,N）的路线最大值）的路线最大值. 删除路径上的点值删除路径上的点值 再求出再求出1个纸条从（个纸条从（M,N） 到（到（1，1）的路线最大值）的路线最大值. 统计两次和统计两次和 上述算法很容易找出反例，如下图。上述算法很容易找出反例，如下图。 第第1次找最优值传递后，导致第次找最优值传递后，导致第2次无法传递。次无法传递。分析 贪心算法错误，因此我们需要同时考虑两个纸条的传递。贪心算法错误，因此我们需要同时考虑两个纸条的传递。 由于由于小渊小渊和小轩的路径可逆，因此，尽管出发点不同，但和小