数字三角形PPT课件_第1页
数字三角形PPT课件_第2页
数字三角形PPT课件_第3页
数字三角形PPT课件_第4页
数字三角形PPT课件_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

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

文档简介

1、分析 你会立刻发现这是一个动态规划的决策问题；每次有两种选择向左和向右，一个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);第1页/共9页递归计算 有了状态转移方程就好办了。 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); 第2页/共9页重叠子问题 这样做是

2、正确的，但是时间效率太低，其原因在于重复计算。1,12,12,23,13,23,23,34,14,24,24,34,24,34,34,4第3页/共9页记忆化搜索 显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。 第4页/共9页记忆化搜索 记忆化搜索把程序分成两部风。首先把d d数组初始化为-1-1； int dp(int i,int j)int dp(int i,int j) memset(d,-1,sizeof(d); memset(d,-1,sizeof(d); if(dij

3、=0) return if(dij=0) return dij;dij; else if(i=n) else if(i=n) return dij=aij; return dij=aij; else return else return dij=aij+max(dp(i+1,j),dpdij=aij+max(dp(i+1,j),dp(i+1,j+1);(i+1,j+1); 时间复杂度为n2;n2;记忆化的功效第5页/共9页动态规划的实质 可以看出动态规划的实质就是 这也就是为什么我们常说动态规划必须满足重叠子问题的原因.记忆化,正符合了这个要求.第6页/共9页递推计算因为在计算 d（i,j）前,它所需要的d(i+1,j)和d(i+1,j+1)一定已经计算出来了。 for(i=1;i=1;i-) for( j=1;jdi+1 j+1) di j=ai j+di+1 j; else di j=ai j+di+

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论