数字三角形学习.pptx

《数字三角形学习.pptx》由会员分享，可在线阅读，更多相关《数字三角形学习.pptx（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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=0)return if(dij=

3、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 j+1;第7页/共9页ENDPOJ1163POJ2760第8页/共9页感谢您的观看！第9页/共9页