信息学奥赛NOIP动态规划入门教学文案课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017,信息学冬令营,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息学奥赛NOIP动态规划入门,引入：走楼梯,已知一个楼梯有n级，从下往上走，一步可以走一级，也可以走两级，走到第N级楼梯有多少种走法？,【输入格式】,一行一个整数n。,【输出格式】,一行仅有一整数，表示走到第n级有多少种走法。,【输入样例】,【输出样例】,2,2,【数据规模】,对100%的数据满足：0 n 30。,最短路径问题,-,求,A,到,E,的最短路的长度,穷举？贪心？搜索？,思考,：,仔细观察本图路径的特殊性，可以分成,4,个阶段：,第一阶段：,A,经过,A-B1,或,A-B2,到,B,第二阶段：,B1,有三条路通,；,B2,有两条通路,阶段,1,阶段,2,阶段,3,阶段,4,思考：倒着推；设,F(x),表示,x,到,E,的最短路径的长度,阶段,4,：,F(D1)=3;F(D2)=4;F(D3)=3,阶段,3,：,F(C1)=minF(D1)+C1,到,D1,的路径长度，,F(D2)+C1,到,D2,的路径长度,F(C2),阶段,1,阶段,2,阶段,3,阶段,4,我们把,F(x),称为当前,x,的,状态,；,在这个例子中每个,阶段,的选择依赖当前的状态，又随即引起状态的,转移,，一个,决策序列,(E D3-C4-B2-A),就是在变化的状态中产生的，故有“,动态,”的含义。,阶段,1,阶段,2,阶段,3,阶段,4,基本概念,阶段,：,问题的过程被分成若干相互联系的部分，我们成为阶段，以便按一定的次序求解。,状态,：,某一阶段的出发位置称为状态，通常一个阶段包含若干状态。,决策,：,对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发，通过一次选择性的行动移至下一个阶段的相应状态。,Int F(int n),if ( n = 0 | n=1 ) return 1;,else return F(n-1) + F(n-2);,时间复杂度？能优化吗？,例,1:,斐波那契（,Fibonacci,）数列,例,1:,斐波那契（,Fibonacci,）数列,/dp,数组，用以保存已经计算过的结果,/dpn,记录,F(n),的结果，,dpn= -1,表示没有计算过,Int F(int n),if ( n = 0 | n=1 ) return 1;,if ( dpn != -1 ) return dpn;,else ,dpn =,F(n-1) + F(n-2);,return dpn;,时间复杂度？,例,2:,数字三角形,一个由非负数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有个数，从第一行的数开始，每次可以选择向左下或是向右下走一格，一直走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？。,数字三角形,格子编号,穷举？贪心？搜索？,数组存储,深搜（递归实现）,程序清单：,void f( int i, int j ),s=s+a i j ;,if ( i=4 ),if ( s max ) max = s;,else ,f( i+1, j ),;,s=s-a i+1 j ;,f( i+1, j+1),;,s=s-a i+1 j+1;,格子编号,分析：考察,设以格子,(i,j),为首的“子三角形”的最大和为,di,j,（我们将不加区别的把这个子问题,(subproblem),本身也称为,di,j,），则原问题的解是,d1,1,我们关心的是从某处出发到底部的最大和：,从,(2,1),点出发的最大和记做,d2,1,;,从,(2,2),点出发的最大和记做,d2,2,;,从（,1,，,1,）出发有两种选择（,2,，,1,）或（,2,，,2,）,在已知,d2,1,和,d2,2,的情况下，应选择较大的一个。,思考,：考虑更一般的情况，当前位置（,i,，,j,）看成一个,状态,，,定义状态（,i,，,j,）的指标函数,d(i,，,j),为从格子（,i,，,j,）出发时能得到的最大和（包含格子（,i,，,j,）本身的值）。,原题的解：？,d,（？，？）,格子编号,d1,，,1,思考,：观察不同状态如何转移的。,从格子（,i,，,j,）出发有两种决策。,如果（,i,，,j,）格子里的值为,a (i,，,j),向左走需要求“从（,i+1,，,j,）出发的最大和”，就是,di+1,，,j,。,向右走需要求“从（,i+1,，,j+1,）出发的最大和”，就是,di+1,，,j+1,。,如何选呢？,思考,：,边界条件？,其中较大的一个，再加上,a(i,j),的值就是,di,j,。,di,j=,ai,j+maxdi+1,j,di+1,j+1,思想：,从上向下思考，从底向上计算,数字三角形,8,13,21,16,23,24,时间复杂度,O,（,n,2,）,在计算,dij,前，,di+1j,di+1j+1,已计算好了！,方法,1,：递推计算,void,solve,(),int,i , j;,for(j = 1; j = 1; i - -),for(j = 1; j = 0) return,dij;,dij,= aij+max(solve ( i+1, j ), solve ( i+1 , j +1) );,return,dij;,时间复杂度,O,（,n,2,）,不必事先确定各状态的计算顺序,方法,3,：记忆化搜索,动态规划,基本思想,建立子问题的描述，建立状态间的转移关系，使用递推或记忆化搜索法来实现。,状态定义,用问题的某些特征参数描述一个子问题。在本题中用,di,j,表示以格子,(i,j),为根的子三角形的最大和。在很多时候，状态描述的细微差别将引起算法的不同。,状态转移方程即状态值之间的递推关系,。这个方程通常需要考虑两个部分：,一是递推的顺序，二是递归边界,（也是递推起点）。,从直接递归和后两种方法的比较可以看出：,重叠子问题,(overlapping subprob-lems),是动态规划展示威力的关键。,考察：,d(1,1),；,d(2,1),；,d(2,2),这些问题的共性：都是求从一个位置出发到底部的最大值；是一个共同的问题。,d(2,1),d(2,2),重叠子问题,考察：,d(1,1),；,d(2,1),；,d(2,2,）；可以发现每个子问题结果都是最优的。,d(2,1),d(2,2),最优子结构,什么是动态规划？,动态规划是求解包含,重叠子问题,的最优化方法,动态规划的性质？,子问题重叠性质：,在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。,最优化子结构性质：,若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。,能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的,无后效性：,即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。,数字三角形,如果数字三角形,(,有负数,),求的是从上到下的和,最接近零,。就不符合无后效性原则。,动态规划的优势,1.,动态规划比穷举具有较少的计算次数,从数塔问题可以看出，层数为,k,时，,穷举算法求路径的条数,2,k,-1,动态规划计算的次数为,:,穷举最多计算到,n=20,，动态规划可以算到,n=100,2.,递归需要很大的栈空间，而动规的递推法不需要栈空间；使用记忆化搜索比较容易书写程序。,思考,：,还有一种思考方法，从下,向上考虑，观察不同状态如何转,移的。从格子（,i,，,j,）出发有两,种决策。,思考：边界情况：？,思考：最后的结果：？,d11=a11,di1=di-11+ai1 ,第,1,列,dii=di-1i-1+aii ,对角线,maxdn1,dn2dnn,d(i,j),为：取,d(i-1,j),和,d(i-1,j-1),中较大的一个加上,a(i,j),的和。,这种方法本质就是递推,例,3:,最大连续子序列和,（,Maximum Continuous Subsequence Sum,）,给定,k,个整数的序列,A,1,A,2,.,A,k,，其任意连续子序列可表示为, A,i, A,i+1, .,A,j,，其中,1 = i = j = k,。最大连续子序列是所有连续子序中元素和最大的一个。,例如给定序列, -2, 11, -4, 13, -5, -2 ,，其最大连续子序列为,11,-4,13,，最大连续子序列和即为,20,。,暴力枚举？时间复杂度为？能优化吗？复杂度？,令状态,dp,i,表示以,Ai,作为末尾的连续序列的最大和（,Ai,必须作为序列的末尾）。,以样例为例，序列, -2, 11, -4, 13, -5, -2 ,，下标分别设为：,0,，,1,，,2,，,3,，,4,，,5,；,dp0,dp1,dp2,dp3,dp4,dp5,问题转换为,dp0,dp1,dpn-1,中的最大者。,最大连续子序列和,（,Maximum Continuous Subsequence Sum,）,dpi,表示以,Ai,作为末尾的连续序列的最大和（,Ai,必须作为序列的末尾）,;,只有两重情况：,1,、这个最大和的连续序列只有一个元素，即以,Ai,开始，以,Ai,结尾；,最大和就是,Ai,本身,。,2,、这个最大和的连续序列有多个元素，从前面某处,Ap,开始（,pi),；一直到,Ai,结尾。,也就是,dpi-1+Ai,;,Ap+Ai-1+Ai=dpi-1+Ai;,最大连续子序列和,（,Maximum Continuous Subsequence Sum,）,转移方程：,dpi= max Ai , dpi-1 + Ai ,边界：,dp0=A0,最大连续子序列和,（,Maximum Continuous Subsequence Sum,）,代码：,dp0 = A0;,for (int i=1 ; i =aj,同时,ji,初始化,d(i)=,1,for,( int i=n-1; i=1 ; i- -,),max=0; k=0;,for (,int j=i+1 ;j=aj,记忆化搜索,边界情况,d(n)=,1,int dp(int i) ,if (di0) return,di,;,di=1;,for (int j=i+1 ; j=aj,di=max(di,dp(j)+1);,return di;,初始化,di,为,-1,结果输出,?,输出序列,void print_ans( int i);,printf(“%d ”,ai);,for (int j=i ; j=aj,& dj=di-1,）,print_ans(j),;,break,；,记忆化搜索：,while,（,k0,）,printf(“%d ,ak);,k=ck;,递推：,程序框架,-,递推,初始化状态值集合,穷举所有的阶段,穷举当前阶段,i,所有可能的状态,j,穷举,j,状态所有对应的,k,种子状态进行决策,Fij=min,或,max,状态,j,所有可能的前状态,输出最优策略,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！,谢谢,!,