动态规划入门PPT.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,#,动态规划,入门,晋江市养正中学 张昱峥,1,三角形的行数大于,1,小于等于,100,，数字为,0,-,99,例题一、数字三角形,7,3,8,8,1,0,2,7,4,4,4,5,2,6,5,在上面的数字三角形中寻找一条从顶部到底边的路径，使得,路径上所经过的数字之和最大。路径上的每一步都只能往左下或,右下走。只需要求出这个最大和即可，不必给出具体路径。,2,输入格式：,5,/,三角形行数。下面是三角形,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,要求输出最大和,3,解题思路：,用二维数组存放数字三角形。,D(,r,j),:,第,r,行第,j,个数字,(r,j,从,1,开始算,),MaxSum(r,j),:,从,D(r,j),到底边的各条路径中，,最佳路径的数字之和。,问题：求,MaxSum(1,1),典型的递归问题。,D(r,j),出发，下一步只能走,D(r+1,j),或者,D(r+1,j+1),。故对于,N,行的三角形：,if,(,r,=,N),MaxSum(r,j),=,D(r,j),else,MaxSum(,r,j),=,Max,MaxSum(r,1,j),MaxSum(r+1,j+1),+,D(r,j),4,int,DMAXMAX;,int,n;,int,MaxSum(int,i,int,j),if(i=n),return,Dij;,int,x,=,MaxSum(i+1,j);,int,y,=,MaxSum(i+1,j+1);,return,max(x,y)+Dij;,数字三角形的递归程序,:,#include,#include,#define,MAX,101,using,namespace,std;,int,main(),int,i,j;,cin,n;,for(i=1;i=n;i+),for(j=1;j,Dij;,cout,MaxSum(1,1),n;,for(i=1;i=n;i+),for(j=1;j,Dij;,maxSumij,=,-1;,cout,MaxSum(1,1),n;,for(i=1;i=n;i+),for(j=1;j,Dij;,for(,int,i,=,1;i,=,1;,-i,),for(,int,j,=,1;,j,=,i;,+j,),maxSumij,=,max(maxSumi+1j,maxSumi+1j+1),+,Dij,cout,maxSum11,endl;,18,4,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,5,2,6,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,19,7,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,5,2,6,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,20,7,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,12,2,6,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,21,7,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,12,10,6,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,22,7,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,12,10,10,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,23,20,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,12,10,10,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,24,20,空间优化,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,13,10,10,5,没必要用二维,maxSum,数组存储每一个,MaxSum(r,j),只要从底层一行行向上,递推，那么只要一维数组,maxSum100,即可,即只要存储一行的,MaxSum,值就,可以。,25,递归到动规的一般转化方法,递归函数有,n,个参数，就定义一个,n,维的数组，数组,的下标是递归函数参数的取值范围，数组元素的值,是递归函数的返回值，这样就可以从边界值开始，,逐步填充数组，相当于计算递归函数值的逆过程。,26,动规解题的一般思路,1.,将原问题分解为子问题,把原问题分解为若干个子问题，子问题和原问题形式相同,或类似，只不过规模变小了。子问题都解决，原问题即解,决,(,数字三角形例）。,子问题的解一旦求出就会被保存，所以每个子问题只需求,解一次。,27,动规解题的一般思路,2.,确定状态,在用动态规划解题时，我们往往将和子问题相,关的各个变量的一组取值，称之为一个“状,态”。一个“状态”对应于一个或多个子问题，,所谓某个“状态”下的“值”，就是这个“状,态”所对应的子问题的解。,28,动规解题的一般思路,2.,确定状态,所有“状态”的集合，构成问题的“状态空间”。“状态,空间”的大小，与用动态规划解决问题的时间复杂度直接相关。,在数字三角形的例子里，一共有,N,(N+1)/2,个数字，所以这个,问题的状态空间里一共就有,N,(N+1)/2,个状态。,整个问题的时间复杂度是状态数目乘以计算每个状态所需,时间。,在数字三角形里每个“状态”只需要经过一次，且在每个,状态上作计算所花的时间都是和,N,无关的常数。,29,动规解题的一般思路,2.,确定状态,用动态规划解题，经常碰到的情况是，,K,个整型变量能,构成一个状态（如数字三角形中的行号和列号这两个变量,构成“状态”）。如果这,K,个整型变量的取值范围分别是,N1,N2,Nk,，那么，我们就可以用一个,K,维的数组,arrayN1,N2Nk,来存储各个状态的“值”。这个,“值”未必就是一个整数或浮点数，可能是需要一个结构,才能表示的，那么,array,就可以是一个结构数组。一个,“状态”下的“值”通常会是一个或多个子问题的解。,30,动规解题的一般思路,3.,确定一些初始状态（边界状态）的值,以“数字三角形”为例，初始状态就是底边数字，值,就是底边数字值。,31,动规解题的一般思路,4.,确定状态转移方程,定义出什么是“状态”，以及在该,“状态”下的“值”后，就要,找出不同的状态之间如何迁移,即如何从一个或多个“值”已知的,“状态”，求出另一个“状态”的“值”,(,“人人为我”递推型,),。状,态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方,程”。,数字三角形的状态转移方程,:,32,能用动规解决的问题的特点,1),2),问题具有最优子结构性质。,如果问题的最优解所包含的,子问题的解也是最优的，我们就称该问题具有最优子结,构性质。,无后效性。,当前的若干个状态值一旦确定，则此后过程,的演变就只和这若干个状态的值有关，和之前是采取哪,种手段或经过哪条路径演变到当前的这若干个状态，没,有关系。,33,例题二：最长上升子序列,问题描述,一个数的序列ai，当a,1,a,2,.,a,S,的时候，我们称这个,序列是上升的。对于给定的一个序列(a,1,a,2,.,a,N,)，我们可,以得到一些上升的子序列(a,i1,a,i2,.,a,iK,)，这里1,=,i1,i2,.,iK,=,N。比如，对于序列(1,7,3,5,9,4,8)，,有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序,列中最长的长度是4，比如子序列(1,3,5,8).,你的任务，就是对于给定的序列，求出最长上升子序列的长度。,34,输入数据,输入的第一行是序列的长度N,(1,=,N,=,1000)。第二行给出,序列中的N个整数，这些整数的取值范围都在0到10000。,输出要求,最长上升子序列的长度。,输入样例,7,1,7,3,5,9,4,8,输出样例,4,35,解题思路,1.找子问题,“求序列的前n个元素的最长上升子序列的长度”是个,子问题，但这样分解子问题，不具有“无后效性”,假设F(n),=,x,但可能有多个序列满足F(n),=,x。有的,序列的最后一个元素比,a,n+1,小，则加上a,n+1,就能形成更长上,升子序列；有的序列最后一个元素不比a,n+1,小以后的事,情受如何达到状态n的影响，不符合“无后效性”,36,解题思路,1.找子问题,“求以a,k,（k=1,2,3N）为终点的最长上升子序列的,长度”,一个上升子序列中最右边的那个数，称为该子序列的,“终点”。,虽然这个子问题和原问题形式上并不完全一样，但,是只要这N个子问题都解决了，那么这N个子问题的解中，,最大的那个就是整个问题的解。,37,2.,确定状态：,子问题只和一个变量-,数字的位置相关。因此序列中数,的位置k,就是“状态”，而状态,k,对应的“值”，就是以a,k,做为“终点”的最长上升子序列的长度。,状态一共有N个。,38,3.,找出状态转移方程：,maxLen,(k)表示以,a,k,做为“终点”的,最长上升子序列的长度那么：,初始状态：maxLen,(1),=,1,maxLen,(k),=,max,maxLen,(i)：1=i,k,且,a,i,N;,for(,int,i,=,1;i,ai;,maxLeni,=,1;,for(,int,i,=,2;,i,=,N;,+i),/,每次求以第,i,个数为终点的最长上升子序列的长度,for(,int,j,=,1;,j,aj,),maxLeni,=,max(maxLeni,maxLenj+1);,cout,sz1,sz2,),int,length1,=,strlen(,sz1);,int,length2,=,strlen(,sz2);,int,nTmp;,int,i,j;,for(,i,=,0;i,=,length1;,i,+,),maxLeni0,=,0;,for(,j,=,0;j,=,length2;,j,+,),maxLen0j,=,0;,46,for(,i,=,1;i,=,length1;i,+,),for(,j,=,1;,j,=,length2;,j,+,),if(,sz1i-1,=,sz2j-1,),maxLenij,=,maxLeni-1j-1,+,1;,else,maxLenij,=,max(maxLenij-1,maxLeni-1j);,cout,maxLenlength1length2,endl;,return,0;,47,怎么输出这个最长公共子序列？,回溯输出,48,7/11/2025,void LCS_LENGTH(char x,char y),int i,j,m=strlen(x),n=strlen(y);,for(i=1;i=m;i+)ci0=0;,for(j=1;j=n;j+)c0j=0;,for(i=1;i=m;i+),for(j=1;j=cij-1),cij=ci-1j;,bij=;,else,cij=cij-1;,bij=;,void LCS(char x,int i,int j),if(i&j),if(bij=),LCS(x,i-1,j-1);,printf(%c,xi-1);,else,if(bij=),LCS(x,i-1,j);,else,LCS(x,i,j-1);,49,7/11/2025,有一个由,1.9,组成的数字串,.,问如果将,m,个加,号插入到这个数字串中,在各种可能形成的,表达式中，值最小的那个表达式的值是多少,例四、最佳加法表达式,50,假定数字串长度是,n,，添完加号后,表达式的最后,一个加号添加在第,i,个数字后面，那么整个表达,式的最小值，就等于在前,i,个数字中插入,m,1,个加号所能形成的最小值，加上第,i,+,1,到第,n,个数字所组成的数的值（,i,从,1,开始算）。,解题思路,51,总时间复杂度：,O(mn,2,),.,解题思路,设,V(m,n),表示在,n,个数字中插入,m,个加号所能形成,的表达式最小值，那么：,if,m,=,0,V(m,n),=,n,个数字构成的整数,else,if,n,m,+,1,V(m,n),=,else,V(m,n),=,Min,V(m-1,i),+,Num(i+1,n),(,i,=,m,n-1),Num(i,j),表示从第,i,个数字到第,j,个数字所组成的数。数字编号从,1,开始算。此操,作复杂度是,O(j-i+1),，可以预处理后存起来。,52,总时间复杂度：,O(mn,2,),.,若,n,比较大，,long,long,不够存放运算过程中的整数，则需要使用高精度计算,（用数组存放大整数，模拟列竖式做加法），复杂度为,O(mn,3,),解题思路,53,例五、神奇的口袋,有一个神奇的口袋，总的容积是40，用这个口袋可以变出一,些物品，这些物品的总体积必须是40。,John现在有n（1n,20）个想要得到的物品，每个物品,的体积分别是a,1,，a,2,a,n,。John可以从这些物品中选择一,些，如果选出的物体的总体积是40，那么利用这个神奇的口,袋，John就可以得到这些物品。现在的问题是，John有多少,种不同的选择物品的方式。,54,3,20,20,20,输入,输入的第一行是正整数,n,(1,=,n,=,20),，表示不同的物品的,数目。接下来的,n,行，每行有一个,1,到,40,之间的正整数，分别,给出,a,1,，,a,2,a,n,的值。,输出,输出不同的选择物品的方式的数目。,输入样例,输出样例,3,55,枚举每个物品是选还是不选，共,2,20,种情况,枚举的解法：,56,int,a30;,int,N;,int,Ways(int,w,int,k,),/,从前,k,种物品中选择一些，凑成体积,w,的做,法数目,if(,w,=,0,),return,1;,if(,k,N;,for(,int,i,=,1;i,ai;,cout,N;,memset(Ways,0,sizeof(Ways);,for(,int,i,=,1;i,ai;,Ways0i,=,1;,Ways00,=,1;,for(,int,w,=,1,;,w,=,40;,+,w,),for(,int,k,=,1;,k,=,0),Wayswk,+=,Waysw-akk-1;,cout,Ways40N;,return,0;,动,规,解,法,58,例六、0-1背包问题,有N件物品和一个容积为M的背包。第i件物品的体积wi,，价值是di。求解将哪些物品装入背包可使价值总和,最大。每种物品只有一件，可以选择放或者不放,(N=3500,M,=,13000)。,59,0-1背包问题,用,Fij,表示取前i种物品，使它们总体积不超过j的,最优取法取得的价值总和。要求FNM,边界：if,(w1,=,0才有第二项),61,0-1背包问题,Fij,=,max(Fi-1j,Fi-1j-wi+di),本题如用记忆型递归，需要一个很大的二维数组，会,超内存。注意到这个二维数组的下一行的值，只用到了,上一行的正上方及左边的值，因此可用滚动数组的思想,，只要一行即可。即可以用一维数组，用“人人为我”,递推型动归实现。,62,0-1背包问题,状态方程改为,f(x)=maxf(x-vi)+ci,，,f(x),前,i,个物品，体积不超过,x,的最大价值,63,例七、滑雪,Michael喜欢滑雪百这并不奇怪，,因为滑雪的确很刺激。,可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，,你不得不再次走上坡或者等待升降机来载你。,Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字,代表点的高度。下面是一个例子,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,=,100)。下面是R行，,每行有C个整数，代表高度h，0=h=10000。输出输出最长区域的长度。,64,输入,输入的第一行表示区域的行数R和列数C,(1,=,R,C,=,100)。下面是R行，每行有C个整数，,代表高度h，0=h,H(i,j),/,H,代表高度,68,希望大家能,活学活用,掌握递归和动态规划的思想，解决问题时灵活应用,69,