资源描述：
《信息学奥赛NOI动态规划入门(C++)培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、动态规划入门上课内容什么是动态规划基本概念斐波那契数列经典的类型最短路径问题---求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)=min{F(D1)+C1到D1的路径长度，F(D2)+C1到D2的路径长度}F(C2)……阶段1阶段2阶段3阶段4我们把F(x)称为当前x的状态；在这个
2、例子中每个阶段的选择依赖当前的状态，又随即引起状态的转移，一个决策序列(E–D3-C4-B2-A)就是在变化的状态中产生的，故有“动态”的含义。阶段1阶段2阶段3阶段4intfib(intn){if(n==1
3、
4、n==2)return1;elsereturnfib(n-1)+fib(n-2);}时间复杂度？能优化吗？例1:斐波那契（Fibonacci）数列斐波纳契数列大量重复计算！如何可以使计算仅需一次？例1:斐波那契（Fibonacci）数列//dp数组，用以保存已经计算过的结果//dp[n]记录F(n)的结果，dp[n]=-1表示没有计算过intf
5、ib(intn){if(n==1
6、
7、n==2)return1;if(dp[n]!=-1)returndp[n];else{dp[n]=fib(n-1)+fib(n-2);returndp[n];}}时间复杂度？基本概念阶段：问题的过程被分成若干相互联系的部分，我们成为阶段，以便按一定的次序求解。状态：某一阶段的出发位置称为状态，通常一个阶段包含若干状态。决策：对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发，通过一次选择性的行动移至下一个阶段的相应状态。例2:数字三角形一个由非负数组成的三角形，第一行只有一个数，除了最下行之外每个数
8、的左下方和右下方各有个数，从第一行的数开始，每次可以选择向左下或是向右下走一格，一直走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？。数字三角形格子编号穷举？贪心？搜索？数组存储深搜（递归实现）程序清单：voidf(inti,intj);{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)为首的“子三角形”的最大和为d[i,j]（我们将不加区别的把这个子问题(su
9、bproblem)本身也称为d[i,j]），则原问题的解是d[1,1]我们关心的是从某处出发到底部的最大和：从(2,1)点出发的最大和记做d[2,1];从(2,2)点出发的最大和记做d[2,2];从（1，1）出发有两种选择（2，1）或（2，2）在已知d[2,1]和d[2,2]的情况下，应选择较大的一个。思考：考虑更一般的情况，当前位置（i，j）看成一个状态，定义状态（i，j）的指标函数d(i，j)为从格子（i，j）出发时能得到的最大和（包含格子（i，j）本身的值）。原题的解：？d（？，？）格子编号d[1，1]思考：观察不同状态如何转移的。从格子（i，j
10、）出发有两种决策。如果（i，j）格子里的值为a(i，j)向左走需要求“从（i+1，j）出发的最大和”，就是d[i+1，j]。向右走需要求“从（i+1，j+1）出发的最大和”，就是d[i+1，j+1]。如何选呢？思考：边界条件？其中较大的一个，再加上a(i,j)的值就是d[i,j]。d[i,j]=a[i,j]+max{d[i+1,j],d[i+1,j+1]}思想：从上向下思考，从底向上计算数字三角形81321162324时间复杂度O（n2）在计算d[i][j]前，d[i+1][j],d[i+1][j+1]已计算好了！方法1：递推计算voidsolve()
11、{inti,j;for(j=1;j<=n;j++)d[n][j]=a[n][j];for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);}dt(1,1)的调用关系树重复计算intsolve(inti,intj){if(i==n)returna[i][j];elsereturna[i][j]+max(solve(i+1,j),solve(i+1,j+1));}方法2：递归计算这样做是正确的，可惜时间效率太低。低效的原因在于重复计算。这个方法和直接递归非
12、常类似，但加入了记忆化(memoization)，保证每个结点只访问一次。//initiall
