1、2022-8-81第第四四讲讲动态规划动态规划（Dynamic programmingDynamic programming）2022-8-82一、一、经典问题经典问题：数塔问题数塔问题 有形如下图所示的数塔，从顶部出发，在每有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。层，要求找出一条路径，使路径上的值最大。2022-8-83用用暴力暴力的方法，可以吗？的方法，可以吗？2022-8-84这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是
2、一个非常庞大的数目（230=10243 109=10亿）。试想一下：试想一下：2022-8-85 拒绝拒绝暴力，暴力，倡导倡导和谐和谐2022-8-86从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，大值是否已经求出才能决策。这样一层一层推下去，直到倒数
3、第二层时就非常明了。直到倒数第二层时就非常明了。如数字如数字2，只要选择它下面较大值的结点，只要选择它下面较大值的结点19前进前进就可以了。所以实际求解时，可从底层开始，层层递就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：2022-8-87思路：从倒数第二行起，思路：从倒数第二行起，按照状态转移方程按照状态转移方程dpij=max(dpi+1j,dpi+1j+1)+valij向上递推，向上递推，直到直到val11，此时此时dp11就是结果就是结果2022-8-
4、88二、二、经典问题经典问题：最长有序子序列：最长有序子序列n问题描述 找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列（注：这里有序指非递减顺序，且不要求子序列连续）。例如，对于序列3,7,1,5,9,3，其中最长有序子序列长度为3，这样的子序列有：3,7,9、1,5,9、3,5,9。2022-8-89二、二、经典问题经典问题：最长有序子序列：最长有序子序列2022-8-810二、二、经典问题经典问题：最长有序子序列：最长有序子序列2022-8-811二、二、经典问题经典问题：最长有序子序列：最长有序子序列2022-8-812三三 11601160 FatMouses S
5、peed FatMouses Speed Problem DescriptionFatMouse believes that the fatter a mouse is,the faster it runs.To disprovethis,you want to take the data on a collection of mice and put as large asubset of this data as possible into a sequence so that the weights are increasing,but the speeds are decreasing
6、.InputInput contains data for a bunch of mice,one mouse per line,terminated byend of file.The data for a particular mouse will consist of a pair of integers:the firstrepresenting its size in grams and the second representing its speed incentimeters per second.Both integers are between 1 and 10000.Th
7、e data ineach test case will contain information for at most 1000 mice.Two mice may have the same weight,the same speed,or even the sameweight and speed.2022-8-813三三 11601160 FatMouses Speed FatMouses Speed nOutputnYour program should output a sequence of lines of data;the first line should contain
8、a number n;the remaining n lines should each contain a single positive integer(each one representing a mouse).If these n integers are m1,m2,.,mn then it must be the case that Wm1 Wm2 .Sm2 .SmnIn order for the answer to be correct,n should be as large as possible.All inequalities are strict:weights m
9、ust be strictly increasing,and speeds must be strictly decreasing.There may be many correct outputs for a given input,your program only needs to find one.2022-8-814三三 11601160 FatMouses Speed FatMouses Speed Sample Input6008 1300 6008 1300 6000 21006000 2100 500 2000 500 2000 1000 4000 1000 4000 110
10、0 3000 1100 3000 6000 2000 6000 2000 8000 1400 8000 1400 6000 1200 6000 1200 2000 1900 2000 1900 Sample Output4 4 5 9 72022-8-815三三 11601160 FatMouses Speed FatMouses Speed 解题思路：解题思路：题目要求找到的体重递增，速度递减题目要求找到的体重递增，速度递减老鼠，先把老鼠的体重进行升序排序老鼠，先把老鼠的体重进行升序排序然后算出速度的最长递减子序列。然后算出速度的最长递减子序列。2022-8-816四四 1087 1087
11、Super Jumping!Jumping!Super Jumping!Jumping!Juping!Juping!nProblem DescriptionnNowadays,a kind of chess game called“Super Jumping!Jumping!Jumping!”is very popular in HDU.Maybe you are a good boy,and know little about this game,so I introduce it to you now.n nThe game can be played by two or more tha
12、n two players.It consists of a chessboard（棋盘）and some chessmen（棋子）,and all chessmen are marked by a positive integer or“start”or“end”.The player starts from start-point and must jumps into end-point finally.In the course of jumping,the player will visit the chessmen in the path,but everyone must jum
13、ps from one chessman to another absolutely bigger(you can assume start-point is a minimum and end-point is a maximum.).And all players cannot go backwards.One jumping can go from a chessman to next,also can go across many chessmen,and even you can straightly get to end-point from start-point.Of cour
14、se you get zero point in this situation.A player is a winner if and only if he can get a bigger score according to his jumping solution.Note that your score comes from the sum of value on the chessmen in you jumping path.Your task is to output the maximum value according to the given chessmen list.2
15、022-8-817四四 1087 1087 Super Jumping!Jumping!Super Jumping!Jumping!Juping!Juping!nInputnInput contains multiple test cases.Each test case is described in a line as follow:N value_1 value_2 value_N It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.A test case sta
16、rting with 0 terminates the input and this test case is not to be processed.n nOutputnFor each case,print the maximum according to rules,and one line one case.2022-8-818四四 1087 1087 Super Jumping!Jumping!Super Jumping!Jumping!Juping!Juping!nSample Inputn3 1 3 2 n4 1 2 3 4 n4 3 3 2 1 n0n nSample Outp
17、utn4 n10 n3解题思路？解题思路？找序列中最大升序子序列的和找序列中最大升序子序列的和 2022-8-820n动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022-8-821n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)
18、T(n/4)T(n/4)2022-8-822n如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022-8-823n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。2022-8-824 问题的最优解包含着其子问题的最优解。这种性质称为最优最优子结构性质子结构性质。在分析问题的最优子结构
19、性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）2022-8-825递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再
20、次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2022-8-826备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。int LookupChain(int i，int j)if(mij 0)return mij;if(i=j)return 0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(int k=i+1;k
21、j;k+)int t=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;2022-8-827五、五、经典问题经典问题：最长公共子序列：最长公共子序列Problem DescriptionA subsequence of a given sequence is the given sequence with some elements(possible none)left out.Given a sequence X=another sequence Z=is a subsequence
22、of X if there exists a strictly increasing sequence of indices of X such that for all j=1,2,.,k,xij=zj.For example,Z=is a subsequence of X=with index sequence.Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.The program input is from a
23、 text file.Each data set in the file contains two strings representing the given sequences.The sequences are separated by any number of white spaces.The input data are correct.For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the
24、beginning of a separate line.2022-8-828五、五、经典问题经典问题：最长公共子序列：最长公共子序列HDOJ-1159HDOJ-1159：Sample Inputabcfbc abfcababcfbc abfcabprogramming contest programming contest abcd mnp abcd mnp Sample OutputSample Output 4 4 2 2 0 02022-8-829若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,
25、2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。2022-8-830设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn
26、且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。2022-8-831由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic;0,;0,0,01,1max1 1102022-8-832a a
27、b bc cf fb bc ca a1 11 11 11 11 11 1b b1 12 22 22 22 22 2f f1 12 22 23 33 33 3c c1 12 23 33 33 34 4a a1 12 23 33 33 34 4b b1 12 23 33 34 44 4辅助空间变化示意图辅助空间变化示意图2022-8-833由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。void LCSLength(int m，int n，char*x，char*y，int*c，int*b)int i，j;for(i=1;i=m;
28、i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);2022-8-834在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij
29、的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。2022-8-835六六、经典问题经典问题：14211421 搬寝室搬寝室Problem Description 搬寝室是很累的,xhd深有体会.时间追述
30、2019年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
31、2022-8-836六六、经典问题经典问题：14211421 搬寝室搬寝室Input每组输入数据有两行,第一行有两个数n,k(2=2*k=n2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于215的正整数).Output对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.2022-8-837六六、经典问题经典问题：14211421 搬寝室搬寝室Sample InputSample Input 2 1 2 1 1 31 3Sample OutputSample Output 4 42022-8-838第一感觉：第一感觉：n根据题目的要求，每次提的两个物根据题目的要求
32、，每次提的两个物品重量差越小越好，是不是每次提品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？的物品一定是重量相邻的物品呢？n证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：n(a-b)2+(c-d)2(a-c)2+(b-d)2n(a-b)2+(c-d)2=2k），如何？如何？nn个物品选二对，个物品选二对，2022-8-842解题思路解题思路n先对物品的重量进行排序，取相邻的物品，将相邻的先对物品的重量进行排序，取相邻的物品，将相邻的物品的差的平方另外存储，得到状态转移方程：物品的差的平方另外存储，得到状态转移方程：dpij=min(dpi-1j,dpi-
33、2j-1+si),nsi是代表是代表i,i+1这两个物品的疲惫度这两个物品的疲惫度.n因为因为si-1,si.代表的是代表的是ai-1,ai,ai+1的疲惫度，中的疲惫度，中间共享了一个间共享了一个ai，所以第二项要用，所以第二项要用dpi-2.2022-8-843参考代码参考代码n#include n#include nusing namespace std;n#define INF 0 x7fffffff nint dp20002000,a2000,s2000;nint main()n int n,k,i,j;n while(scanf(%d%d,&n,&k)!=EOF)n for(i=1
34、;i=n;i+)n scanf(%d,&ai);n sort(a,a+n+1);n for(i=1;i=n;i+)n for(j=1;j=n/2;j+)n dpij=INF;n for(i=2;i=n;i+)n si=(ai-ai-1)*(ai-ai-1);n for(i=2;i=n;i+)n for(j=1;j=i/2;j+)n dpij=min(dpi-1j,dpi-2j-1+si);n printf(%dn,dpnk);n n return 0;n 2022-8-844七、七、经典问题经典问题：1058 1058 Humble NumbersHumble NumbersProblem D
35、escription Problem Description A number whose only prime factors are 2,3,5 A number whose only prime factors are 2,3,5 or 7 is called a humble number.The or 7 is called a humble number.The sequence 1,2,3,4,5,6,7,8,9,10,12,sequence 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,.14,15,16,18,20,21
36、,24,25,27,.shows the first 20 humble numbers.shows the first 20 humble numbers.Write a program to find and print the nth Write a program to find and print the nth element in this sequence element in this sequence 2022-8-845七、七、经典问题经典问题：1058 1058 Humble NumbersHumble NumbersInputThe input consists of
37、 one or more test cases.Each test case consists of one integer n with 1=n?n1-2=min(1*2,1*3,1*5,1*7)n1-2-3=min(2*2,1*3,1*5,1*7)n1-2-3-4=min(2*2,2*3,1*5,1*7)n1-2-3-4-5=min(3 3*2,2 2*3,1*5,1*7)2022-8-848状态转移方程？状态转移方程？nF(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特别的：i,j,k,m 只有在本项被选中后才移动2022-8-849关键问题
38、：关键问题：n这个题目的哪些这个题目的哪些经验值得我们借经验值得我们借鉴？鉴？2022-8-850八八 免费馅饼免费馅饼 11762022-8-851八八 免费馅饼免费馅饼 1176Problem Description都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现
39、实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）2022-8-852八八 免费馅饼免费馅饼 1176Input输入数据有多组。每组数据的第一行为以正整数n(0n100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0T100000),表示在第T秒有一个馅饼掉在
40、x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。Output每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。2022-8-853八八 免费馅饼免费馅饼 1176Sample Input65 1 4 1 6 1 7 2 7 2 8 3 0 Sample Output42022-8-854如何解决？如何解决？请发表见解请发表见解 2022-8-855解题思路解题思路n有点类似于数塔nDpti=MAX(Dpt-1i-1,Dpt-1i,Dpt-1i+1)+DATAti;2022-8-856自学题自学题请大家自学课本P239 最短路径问题P247 插入乘号问题2022-8-857如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。小结小结：DPDP的基本思想的基本思想
