算法设计与分析 课件 5.2-动态规划引例2-数字三角形问题

信息工程大学算法设计与分析动态规划—引例—数字三角形问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版数字三角形问题：求一自塔顶到塔底的路径，该路径上结点值的和最大。138111015469522161417712规定：1.每一步可沿线向左下或右下走；2.1＜三角形高度≤100；3.三角形中的数字为整数，取值区间为[1,99]。1.穷举法假定三角形高度为n，共2n-1条路径，时间复杂度高达O(n2n-1)。1381110154695221614177122.贪心法：每次选值大的边走。从上往下走：13+11+10+9+17=60，不是最优解从下往上走：17+9+15+8+13=62，是最优解，虽然该方法对于本实例可以得到正确解，但不适用于所有实例。138111015469522161417712试想一下，如果已经得到了11和8到塔底的最优路径，那么13到塔底的最优路径是什么呢？13811101546952216141771213到塔底的最优路径=13+max(11和8到塔底的最优路径）变换：把左边一列对齐，塔顶位于第1行第1列。结论：某个数到塔底的最优路径等于该数+max{其左下方的数到塔底的最优路径，其右下方的数到塔底的最优路径}138111015469522161417712令f(i,j)表示第i行第j列的数到塔底的最优路径值，则问题转化为求f(1,1)。f(i,j)=?f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<nf(i,j)表示第i行第j列的数到塔底的最优路径值。a[i,j]存储第i行第j列中的数;结论：某个数到塔底的最优路径等于该数+max{其左下方的数到塔底的最优路径，其右下方的数到塔底的最优路径}138111015469522161417712思考：上述递归代码有什么缺点？递归实现:inta[n+1][n+1];/*n表示总行数，a[i][j]是第i行第j列的值*/int

f(inti,intj)/*返回a[i][j]到塔底的最优路径上的结点和*/{if(i==n)returna[i][j];

returna[i][j]+max(f(i+1,j),f(i+1,j+1));}f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<n方法一：递归实现递归实现的缺点：递归深度大可能导致系统栈溢出。时间复杂度高。有很多子问题被重复计算！T(n)=2T(n-1)+O(1)=O(2n)f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<n方法一：递归实现138111015469522161417712思考：如何解决上述问题？62494122164936261434127172238两种实现方式：带记忆的递归实现（备忘录）自底向上的非递归实现1381110154695221614177121.inta[n+1][n+1];2.intf[n+1][n+1];/*f[i][j]初始为0*/3.int

Demo(inti,intj){4.if(i==n)f[i][j]=a[i][j];5.elseif(f[i][j]==0)6.f[i][j]=a[i][j]+max(Demo(i+1,j),Demo(i+1,j+1));7.returnf[i][j];8.}1.inta[n+1][n+1];2.intf[n+1][n+1];3.int

DP(){4.for(j=1;j<=n;j++) f[n][j]=a[n][j];5.for(i=n-1;i>=1;i--)6. for(j=1;j<=i;j++)7.f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);8.returnf[1][1];9.}方法二：带记忆的递归实现（备忘录）方法三：自底向上的非递归实现单选题。方法三（自底向上的非递归实现）求解数字三角形问题的时间复杂度是多少？A.O(n)B.O(n2)C.O(2n)D.O(1)问题1：如何得到最优解？138111015469522161417712问题2：

如果只要求求解最优值，空间可以优化吗？提示：使用一维数组，从左到右依次计算。138111015469522161