资源描述：
《动态规划算法初步(修改)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划算法初步1前言：各类信息学竞赛的重要考察内容。不同于其他算法和数据结构，没有有固定的结构框架。对选手能力有较高要求（数学）。初学者不易掌握其思想，需要做大量的题。典型的问题。会做不代表真正掌握。主要分析问题的方法和思路；其次是代码。2在三个竞赛中的首次出现：数字三角形【IOI1994】石子合并【NOI1995】导弹拦截【NOIP1999】3目录：两个引例动态规划的基本概念动态规划的常见模型及例题4引例1：数字三角形【IOI1994】有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向
2、左下或右下方向走。下图数据的路应为7->3->8->7->5，和为30。输入：第一行：n(1<=n<=100),数字三角形共有n行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和的最大值。73881027444526556输入样例：5738810274445265输出样例：30样例：i,ji+1,ji+1,j+178路径数字最大和：7+3+8+7+5=309深度优先搜索算法：Proceduredfs(i,j,sum)//从(1,1)走到（i，j）位置所求和sumBeg
3、inifi=nthen//走到最后一行ans=max(ans,sum);exit;dfs(向左下方走)；dfs(向右下方走)；End;10代码实现：//二维数组a[i,j]存储数字三角形。proceduredfs(i,j,sum:integer);beginifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;初始：dfs(1,1,a[1,1]);结果：ansi,ji+1,ji+1,
4、j+111i,ji+1,ji+1,j+1n<=100超时！12N=109263531825146385932588470293882535020119968561497607471333951962796078786124494136303223163231325676748313每个位置被计算过的次数：1111211331146411510105116152015611721353521711828567056288119368412612684369114代码实现：//二维数组a[i,j]存储数字三角形。procedured
5、fs(i,j,sum:integer);begininc(count[i,j]);//计数器ifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;i,ji+1,ji+1,j+115搜索速度慢的原因是做了很多重复的计算实际上：从（i,j）走到最后一行；路线上和的最大值不变。926353182514638593258847029388253502011996856149760747133
6、3951962796078786124494136303223163231325676748316所以：第一次求完(i,j)到达最后一行的最大值后，用f[i,j]记录下来。以后再遇到时无需再求，可直接拿过来使用。大大的节省时间。记忆化搜索17记忆化搜索算法：//a[i,j]记录数字三角形//f[i,j]:从(i,j)走到最后一行的和的最大值；初始-1Proceduredfs(i,j:integer);//求(i,j)到最后一行的最大和beginifi=nthenbeginf[i,j]:=a[i,j];exit;end;iff[i
7、,j]>=0thenexit;//已经求过了，无需再求dfs(i+1,j);dfs(i+1,j+1);f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];end;dfs(1,1);ans=f[1,1];18i,ji+1,ji+1,j+1每个点的计算次数：n=101111111111111111111111111111111111111111111110000000000N<=100;问题解决了19思考记忆化搜索的求解过程：i,ji+1,ji+1,j+1……20f[i,j]:(i,j)到最后一行的和的最
8、大值；Ans=f[1,1]换一种方法实现：//f[i,j]：从(i,j)走到最后一行的和的最大值；fori:=1tondof[n,i]:=a[n,i];//最后一行fori:=n-1downto1do//从第n-1行向上求forj:=1toidof[i,j]:=
