《信息学奥赛NOI动态规划入门（C）培训讲学课件.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛NOI动态规划入门（C）培训讲学课件.ppt（63页珍藏版）》请在三一办公上搜索。
1、信息学奥赛NOI动态规划入门(C+)培训讲学,46、法律有权打破平静。马格林47、在一千磅法律里，没有一盎司仁爱。英国48、法律一多，公正就少。托富勒49、犯罪总是以惩罚相补偿；只有处罚才能使犯罪得到偿还。达雷尔50、弱者比强者更能得到法律的保护。威厄尔,信息学奥赛NOI动态规划入门(C+)培训讲学信息学奥赛NOI动态规划入门(C+)培训讲学46、法律有权打破平静。马格林47、在一千磅法律里，没有一盎司仁爱。英国48、法律一多，公正就少。托富勒49、犯罪总是以惩罚相补偿；只有处罚才能使犯罪得到偿还。达雷尔50、弱者比强者更能得到法律的保护。威厄尔动态规划入门上课内容什么是动态规划基本概念斐波那
2、契数列经典的类型,动态规划入门,上课内容什么是动态规划基本概念斐波那契数列经典的类型,(D1B1(c2D2EB2D3阶段1阶段4阶段2阶段3思考:仔细观察本图路径的特殊性,可以分成4个阶段第一阶段:A经过A-B1或AB2到B第二阶段:B1有三条路通,;B2有两条通路,(c2c阶段1阶段2阶段3、阶段4思考:倒着推;设F()表示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),856396481011,(Bl(c2(D之阶段1阶段2阶段3阶段4我们把F(x)称为当前x
3、的状态;在这个例子中每个阶段的选择依赖当前的状态,又随即引起状态的转移,一个决策序列(E-D3-C4B2-A就是在变化的状态中产生的,故有“动态”的含义。,例士:斐波那契( Fibonacci)数列int fib(int n)if(n=1 n=2 )return 1:else return fib(n-1)+ fib(n-2)时间复杂度?能优化吗,斐波纳契数列fib(6fib(5)fib(fb(4)fib (3)fib(3)b(2而2m(和区m(1和b区2fb(1大量重复计算如何可以使计算仅需次?,例士:斐波那契( Fibonacci)数列/dp数组,用以保存已经计算过的结果/dpn记录F(n)的结果,dpn=-1表示没有计算过int fib(int n)(if(n=ln=2)return 1if( dpn! =-1)return dpn:lse idpn= fib(n-1)+fib(n-2)return dpn:时间复杂度,END,16、业余生活要有意义，不要越轨。华盛顿17、一个人即使已登上顶峰，也仍要自强不息。罗素贝克18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。马云19、自己活着，就是为了使别人过得更美好。雷锋20、要掌握书，莫被书掌握；要为生而读，莫为读而生。布尔沃,
