信息学奥赛NOIP动态规划入门ppt课件.pptx

动态规划初步,引入：走楼梯,已知一个楼梯有n级，从下往上走，一步可以走一级，也可以走两级，走到第N级楼梯有多少种走法？【输入格式】 一行一个整数n。 【输出格式】 一行仅有一整数，表示走到第n级有多少种走法。【输入样例】 【输出样例】2 2【数据规模】对100%的数据满足：0 n 30。,最短路径问题-求A到E的最短路的长度,穷举？贪心？搜索？,思考： 仔细观察本图路径的特殊性，可以分成4个阶段：第一阶段：A经过A-B1或A-B2到B第二阶段：B1有三条路通；B2有两条通路,思考：倒着推；设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),我们把F(x) 称为当前x的状态； 在这个例子中每个阶段的选择依赖当前的状态，又随即引起状态的转移，一个决策序列(E D3-C4-B2-A)就是在变化的状态中产生的，故有“动态”的含义。,基本概念,阶段： 问题的过程被分成若干相互联系的部分，我们成为阶段，以便按一定的次序求解。状态： 某一阶段的出发位置称为状态，通常一个阶段包含若干状态。决策： 对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发，通过一次选择性的行动移至下一个阶段的相应状态。,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（n2） 在计算dij前，di+1j,di+1j+1已计算好了！,方法1：递推计算,void solve ()int i , j;for(j = 1; j = 1; i - -)for(j = 1; j = i; j +)dij = aij + max (di +1 j, di +1 j +1);,dt(1,1) 的调用关系树,重复计算,int solve ( int i , int j)if (i = n) return aij; else return aij + max( solve (i+1,j), solve (i+1 , j +1);,方法2：递归计算,这样做是正确的，可惜时间效率太低。低效的原因在于重复计算。,这个方法和直接递归非常类似，但加入了记忆化(memoization) ，保证每个结点只访问一次。/ initially , all dij are -1int solve ( int i , int j)if( i = n ) return aij;if(d i j = 0) return dij;dij = aij+max(solve ( i+1, j ), solve ( i+1 , j +1) );return dij;,时间复杂度O（n2） 不必事先确定各状态的计算顺序,方法3：记忆化搜索,动态规划基本思想,建立子问题的描述，建立状态间的转移关系，使用递推或记忆化搜索法来实现。,状态定义用问题的某些特征参数描述一个子问题。在本题中用di,j表示以格子(i,j)为根的子三角形的最大和。在很多时候，状态描述的细微差别将引起算法的不同。状态转移方程即状态值之间的递推关系。这个方程通常需要考虑两个部分：一是递推的顺序，二是递归边界（也是递推起点）。从直接递归和后两种方法的比较可以看出：重叠子问题(overlapping subprob-lems) 是动态规划展示威力的关键。,考察：d(1,1)；d(2,1)；d(2,2)这些问题的共性：都是求从一个位置出发到底部的最大值；是一个共同的问题。,重叠子问题,考察：d(1,1)；d(2,1)；d(2,2）；可以发现每个子问题结果都是最优的。,最优子结构,什么是动态规划？,动态规划是求解包含重叠子问题的最优化方法,动态规划的性质？ 子问题重叠性质：在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。 最优化子结构性质：若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。 能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的,无后效性：即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。,数字三角形,如果数字三角形(有负数)求的是从上到下的和最接近零。就不符合无后效性原则。,动态规划的优势,1.动态规划比穷举具有较少的计算次数 从数塔问题可以看出，层数为k时， 穷举算法求路径的条数2k-1 动态规划计算的次数为: 穷举最多计算到n=20，动态规划可以算到n=1002.递归需要很大的栈空间，而动规的递推法不需要栈空间；使用记忆化搜索比较容易书写程序。,思考： 还有一种思考方法，从下 向上考虑，观察不同状态如何转 移的。从格子（i，j）出发有两 种决策。,思考：边界情况：？,思考：最后的结果：？,d11=a11di1=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个整数的序列A1,A2,.,Ak ，其任意连续子序列可表示为 Ai, Ai+1, .,Aj ，其中 1 = i = j = k。最大连续子序列是所有连续子序中元素和最大的一个。 例如给定序列 -2, 11, -4, 13, -5, -2 ，其最大连续子序列为11,-4,13，最大连续子序列和即为20。 暴力枚举？时间复杂度为？能优化吗？复杂度？,令状态dpi表示以Ai作为末尾的连续序列的最大和（Ai必须作为序列的末尾）。以样例为例，序列 -2, 11, -4, 13, -5, -2 ，下标分别设为：0，1，2，3，4，5；dp0dp1dp2dp3dp4dp5问题转换为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 n ; i+) dpi= max ( Ai , dpi-1 + Ai ) 结果？,动态规划的核心,设计状态 和状态转移方程,问题描述：拦截导弹（NOIP1999）： 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？,样例输入： 8 389 207 155 300 299 170 158 65 样例输出： 6（最多能拦截的导弹数）,例4：最长下降序列,题目分析： 给定一个正整数序列，求出其中最长下降序列：例如：389 207 155 300 299 170 158 65389 300 299 170 158 65所求的问题：从某一个位置开始的最长下降序列寻找一个状态？,设d(i)表示从结点i出发的最长下降序列,从d(1)位置出发，考察下一步：,389 207 155 300 499 170,d(1)=Maxd(2)、d(3)、d(4)、d(6)+1,考虑更一般的情况：,d(i)=,Maxd(j)+1 并且ai=aj同时ji,初始化,d(i)=,1,for ( int i=n-1; imax) max=dj; k=j; ; di=max+1; ci=k; 记录前驱,从n-1开始递推,考虑更一般的情况：,d(i)=,Maxd(j)+1 并且ai=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 break； ,记忆化搜索：,while （ k0） printf(“%d ,ak); k=ck; ,递推：,程序框架-递推,初始化状态值集合 穷举所有的阶段 穷举当前阶段i所有可能的状态j 穷举j状态所有对应的k种子状态进行决策 Fij=min或max状态j所有可能的前状态 输出最优策略,