数字三角形.ppt_第1页
数字三角形.ppt_第2页
数字三角形.ppt_第3页
数字三角形.ppt_第4页
数字三角形.ppt_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

数字三角形,给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条 路,使得所经过的权值之和最小或 者最大.,分析,你会立刻发现这是一个动态规划的决策问题；每次有两种选择向左和向右，一个n层的数字三角形完整路线有2n条，所以当n比较大的时候，用回溯法是行不通滴。 如果用d(i,j)为从格子（i,j）出发时得到的最大和（包括格子（i，j）本身），那么可以得到状态转移方程： d(i,j)=a(i,j)+maxd(i+1,j),d(i+1,j+1);,递归计算,有了状态转移方程就好办了。 int dp(int i,int j) if(i=n) return dij=aij; else return dij+=max(dp(i+1,j),dp(i+1,j+1); ,重叠子问题,这样做是正确的，但是时间效率太低，其原因在于重复计算。,1,1,2,1,2,2,3,1,3,2,3,2,3,3,4,1,4,2,4,2,4,3,4,2,4,3,4,3,4,4,记忆化搜索,显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。,记忆化搜索,记忆化搜索把程序分成两部风。首先把d数组初始化为-1； int dp(int i,int j) memset(d,-1,sizeof(d); if(dij=0) return dij; else if(i=n) return dij=aij; else return dij=aij+max(dp(i+1,j),dp(i+1,j+1); 时间复杂度为n2;,记忆化的功效,动态规划的实质,可以看出动态规划的实质就是 这也就是为什么我们常说动态规划必须满足重叠子问题的原因.记忆化,正符合了这个要求.,记忆化搜索,递推计算,因为在计算 d（i,j）前,它所需要的d(i+1,j)和d(i+1,j+1)一定已经计算出来了。 for(i=1;i=1;i-) for(j=1;jdi+1j+1) dij=aij+di
人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论