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

1、信息学奥赛NOIP动态规划入门引入：走楼梯引入：走楼梯已知一个楼梯有已知一个楼梯有n n级，从下往上走，一步可以走一级，也可以走两级，走到级，从下往上走，一步可以走一级，也可以走两级，走到第第NN级楼梯有多少种走法？级楼梯有多少种走法？【输入格式】【输入格式】一行一个整数一行一个整数n n。【输出格式】【输出格式】一行仅有一整数，表示走到第一行仅有一整数，表示走到第n n级有多少种走法。级有多少种走法。【输入样例】【输入样例】【输出样例】【输出样例】2 2 2 2【数据规模】【数据规模】对对100%100%的数据满足：的数据满足：0 0 n 30 n 30。最短路径问题最短路径问题-求求A A

2、到到E E的最短路的长度的最短路的长度穷举？贪心？搜索？思考思考：仔细观察本图路径的特殊性，可以分成仔细观察本图路径的特殊性，可以分成4 4个阶段：个阶段：第一阶段：第一阶段：A A经过经过A-B1A-B1或或A-B2A-B2到到B B第二阶段：第二阶段：B1B1有三条路通有三条路通；B2B2有两条通路有两条通路阶段阶段1阶段阶段2阶段阶段3阶段阶段4思考：倒着推；设F(x)表示x到E的最短路径的长度阶段阶段4 4：F(D1)=3;F(D2)=4;F(D3)=3F(D1)=3;F(D2)=4;F(D3)=3阶段阶段3 3：F(C1)=minF(D1)+C1F(C1)=minF(D1)+C1到到

3、D1D1的路径长度，的路径长度，F(D2)+C1 F(D2)+C1到到D2D2的路径长度的路径长度 F(C2)F(C2)阶段阶段1阶段阶段2阶段阶段3阶段阶段4 我们把我们把F(x)F(x)称为当前称为当前x x的的状态状态；在这个例子中每个在这个例子中每个阶段阶段的选择依赖当前的状态，又的选择依赖当前的状态，又随即引起状态的随即引起状态的转移转移，一个，一个决策序列决策序列(E D3-C4-(E D3-C4-B2-A)B2-A)就是在变化的状态中产生的，故有就是在变化的状态中产生的，故有“动态动态”的的含义。含义。阶段阶段1阶段阶段2阶段阶段3阶段阶段4基本概念基本概念阶段阶段：问题的过程被

4、分成若干相互联系的部分，我问题的过程被分成若干相互联系的部分，我们成为阶段，以便按一定的次序求解。们成为阶段，以便按一定的次序求解。状态状态：某一阶段的出发位置称为状态，通常一个阶某一阶段的出发位置称为状态，通常一个阶段包含若干状态。段包含若干状态。决策决策：对问题的处理中作出的每种选择的行动就是对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发，通过一次决策。即从该阶段的每个状态出发，通过一次选择性的行动移至下一个阶段的相应状态。选择性的行动移至下一个阶段的相应状态。Int F(int n)if(n=0|n=1)return 1;else return F(n-1)+F(n

5、-2);时间复杂度？能优化吗？例例1:1:斐波那契（斐波那契（FibonacciFibonacci）数列）数列例例1:1:斐波那契（斐波那契（FibonacciFibonacci）数列）数列/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:数字三角形一个由非负数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有个数，从第一行的数开始，每次可

6、以选择向左下或是向右下走一格，一直走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？。数字三角形格子编号穷举？贪心？搜索？数组存储深搜（递归实现）程序清单：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

7、,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）出发的最大和”，就是

8、di+1，j+1。如何选呢？思考思考：边界条件？边界条件？其中较大的一个，再加上a(i,j)的值就是di,j。di,j=ai,j+maxdi+1,j,di+1,j+1思想：思想：从上向下思考，从底向上计算从上向下思考，从底向上计算数字三角形81321162324时间复杂度O（n2）在计算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（n2）不必事先确

9、定各状态的计算顺序方法3：记忆化搜索动态规划基本思想 建立子问题的描述，建立状态间的转移关系，使用递推或记忆化搜索法来实现。状态定义用问题的某些特征参数描述一个子问题。在本题中用di,j表示以格子(i,j)为根的子三角形的最大和。在很多时候，状态描述的细微差别将引起算法的不同。状态转移方程即状态值之间的递推关系。这个方程通常需要考虑两个部分：一是递推的顺序，二是递归边界（也是递推起点）。从直接递归和后两种方法的比较可以看出：重叠子问题(overlapping subprob-lems)是动态规划展示威力的关键。考察：d(1,1)；d(2,1)；d(2,2)这些问题的共性：都是求从一个位置出发到

10、底部的最大值；是一个共同的问题。d(2,1)d(2,1)d(2,2)d(2,2)重叠子问题考察：d(1,1)；d(2,1)；d(2,2）；可以发现每个子问题结果都是最优的。d(2,1)d(2,1)d(2,2)d(2,2)最优子结构什么是动态规划？什么是动态规划？动态规划是求解包含动态规划是求解包含重叠子问题重叠子问题的最优化方法的最优化方法 动态规划的性质？动态规划的性质？子问题重叠性质：子问题重叠性质：在用递归算法自顶向下对问题进行在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法

11、利用此性质，对每个可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。子问题只计算一次，然后将其结果保存起来以便高效重用。最优化子结构性质：最优化子结构性质：若问题的最优解所包含的子问题若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。足最优化原理）。能用动态规划解决的求最优解问题，必须满足最优能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的解的每个局部也都是最优的 无后效性：无后效性：即某阶段的状态一旦确定，则此后过程的即某阶段的

12、状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，演变不再受此前各状态及决策的影响。也就是说，“未未来与过去无关来与过去无关”，当前的状态是此前历史的一个完整总，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的结，此前的历史只能通过当前的状态去影响过程未来的演变。演变。数字三角形 如果数字三角形如果数字三角形(有有负数负数)求的是从上到下求的是从上到下的和的和最接近零最接近零。就不。就不符合无后效性原则。符合无后效性原则。动态规划的优势动态规划的优势1.1.动态规划比穷举具有较少的计算次数动态规划比穷举具有较少的计算次数 从数塔问题可以看出，

13、层数为从数塔问题可以看出，层数为k k时，时，穷举算法求路径的条数穷举算法求路径的条数2 2k k-1-1 动态规划计算的次数为动态规划计算的次数为:穷举最多计算到穷举最多计算到n=20n=20，动态规划可以算到，动态规划可以算到n=100n=1002.2.递归需要很大的栈空间，而动规的递推法不需要栈空间；使用记忆化搜索递归需要很大的栈空间，而动规的递推法不需要栈空间；使用记忆化搜索比较容易书写程序。比较容易书写程序。2)1(kk思考思考：还有一种思考方法，从下还有一种思考方法，从下 向上考虑，观察不同状态如何转向上考虑，观察不同状态如何转 移的。从格子（移的。从格子（i i，j j）出发有两

14、）出发有两 种决策。种决策。思考：边界情况：？思考：边界情况：？思考：最后的结果：？思考：最后的结果：？d11=a11d11=a11di1=di-11+ai1 di1=di-11+ai1 第第1 1列列 dii=di-1i-1+aii dii=di-1i-1+aii 对角线对角线 maxdn1,dn2dnnd(i,j)d(i,j)为：取为：取d(i-1,j)d(i-1,j)和和d(i-1,j-1)d(i-1,j-1)中较中较大的一个加上大的一个加上a(i,j)a(i,j)的和。的和。这种方法本这种方法本质就是递推质就是递推例例3:3:最大连续子序列和最大连续子序列和（Maximum Conti

15、nuous Subsequence SumMaximum Continuous Subsequence Sum）n给定k个整数的序列A1,A2,.,Ak，其任意连续子序列可表示为 Ai,Ai+1,.,Aj，其中 1=i=j=k。最大连续子序列是所有连续子序中元素和最大的一个。n 例如给定序列-2,11,-4,13,-5,-2，其最大连续子序列为11,-4,13，最大连续子序列和即为20。n 暴力枚举？时间复杂度为？能优化吗？复杂度？暴力枚举？时间复杂度为？能优化吗？复杂度？令状态令状态dpidpi表示以表示以AiAi作为末尾的连续序列的最大和（作为末尾的连续序列的最大和（AiAi必须作为序必须

16、作为序列的末尾）。列的末尾）。以样例为例，序列以样例为例，序列-2,11,-4,13,-5,-2 -2,11,-4,13,-5,-2，下标分别设为：，下标分别设为：0 0，1 1，2 2，3 3，4 4，5 5；dp0dp0dp1dp1dp2dp2dp3dp3dp4dp4dp5dp5问题转换为问题转换为dp0,dp1,dpn-1dp0,dp1,dpn-1中的最大者。中的最大者。最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum）dpidpi表示以表示以AiAi作为末尾的连续序

17、列的最大和（作为末尾的连续序列的最大和（AiAi必须作为序列的末尾）必须作为序列的末尾）;只有两重情况：只有两重情况：1 1、这个最大和的连续序列只有一个元素，即以、这个最大和的连续序列只有一个元素，即以AiAi开始，以开始，以AiAi结尾；结尾；最最大和就是大和就是AiAi本身本身。2 2、这个最大和的连续序列有多个元素，从前面某处、这个最大和的连续序列有多个元素，从前面某处ApAp开始（开始（pi)pi)；一直；一直到到AiAi结尾。结尾。也就是也就是 dpi-1+Aidpi-1+Ai;Ap+Ai-1+Ai=dpi-1+Ai;Ap+Ai-1+Ai=dpi-1+Ai;最大连续子序列和最大连续

18、子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum）n转移方程：dpi=max Ai,dpi-1+Ai 边界：dp0=A0最大连续子序列和最大连续子序列和（Maximum Continuous Subsequence SumMaximum Continuous Subsequence Sum）n代码：代码：dp0=A0;for(int i=1;i=aj同时ji 初始化 d(i)=1 for for(int i=n-1;i=1;i-(int i=n-1;i=1;i-)max=0;k=0;max=0;k

19、=0;for(for(int j=i+1;j=n;j+int j=i+1;j=n;j+)if(if(ajmaxajmax)max=dj;k=j;max=dj;k=j;di=di=max+1max+1;ci=k;ci=k;记录前驱记录前驱 从从n-1n-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 pr

20、int_ans(int i);void print_ans(int i);printf(“%d”,ai);printf(“%d”,ai);for(int j=i;j=n;j+)for(int j=i;j=ajai=aj&dj=di-1&dj=di-1）print_ans(j)print_ans(j);breakbreak；记忆化搜索：while while（k0 k0）printf(“%d,ak);printf(“%d,ak);k=ck;k=ck;递推：程序框架程序框架-递推递推初始化状态值集合 穷举所有的阶段 穷举当前阶段i所有可能的状态j 穷举j状态所有对应的k种子状态进行决策 Fij=min或max状态j所有可能的前状态 输出最优策略此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！感谢您的支持，我们努力做得更好！谢谢谢谢!