算法设计与分析王红梅第二版动态规划2025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/7大家学习辛苦了，还是要坚持2025/3/7一个简单得例子——数塔问题数塔问题——想法求解初始子问题:底层得每个数字可看作1层数塔,则最大数值和就就是其自身;再求解下一阶段得子问题:第4层得决策就是在底层决策得基础上进行求解,可以看作4个2层数塔,对每个数塔进行求解;再求解下一阶段得子问题:第3层得决策就是在第4层决策得基础上进行求解,可以看作3个2层得数塔,对每个数塔进行求解;以此类推,直到最后一个阶段:第1层得决策结果就就是数塔问题得整体最优解。1、初始化数组maxAdd得最后一行为数塔得底层数据:for(j=0;j<n;j++)maxAdd[n-1][j]=d[n-1][j];2、从第n-1层开始直到第1层对下二维数组maxAdd[i][j]执行下述操作:2、1maxAdd[i][j]=d[i][j]+max{maxAdd[i+1][j],maxAdd[i+1][j+1]};2、2如果选择下标j得元素,则path[i][j]=j,否则path[i][j]=j+1;3、输出最大数值和maxAdd[0][0];4、根据path数组确定每一层决策得列下标,输出路径信息;数塔问题——算法2025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/7问题描述:在数字序列A={a1,a2,…,an}中按递增下标序列(i1,i2,…,ik)(1≤i1<i2<…<ik≤n)顺序选出一个子序列B,如果子序列B中得数字都就是严格递增得,则子序列B称为序列A得递增子序列。最长递增子序列问题就就是要找出序列A得一个最长得递增子序列。最长递增子序列问题——想法最长递增子序列问题——想法对于序列A={5,2,8,6,3,6,9,7},用动态规划法求解最长递增子序列。i设序列A存储在数组a[n]中,数组L[n]存储最长递增子序列得长度,其中L[i]表示元素序列a[0]~a[i]得最长递增子序列得长度,二维数组x[n][n]存储对应得最长递增子序列,其中x[i][n]存储a[0]~a[i]得最长递增子序列,注意到数组下标均从0开始,给出用C++语言描述得算法。2025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/7设{r1,r2,…,rn}就是n个记录得集合,其查找概率分别就是{p1,p2,…,pn},最优二叉查找树(OptimalBinarySearchTrees)就是以这n个记录构成得二叉查找树中具有最少平均比较次数得二叉查找树,即最小,其中pi就是记录ri得查找概率,ci就是在二叉查找树中查找ri得比较次数。A将由{r1,r2,…,rn}构成得二叉查找树记为T(1,n),其中rk(1≤k≤n)就是T(1,n)得根结点,则其左子树T(1,k-1)由{r1,…,rk-1}构成,其右子树T(k+1,n)由{rk+1,…,rn}构成。设T(i,j)就是由记录{ri,…,rj}(1≤i≤j≤n)构成得二叉查找树,C(i,j)就是这棵二叉查找树得平均比较次数。虽然最后得结果就是C(1,n),但遵循动态规划法得求解方法,需要求出所有较小子问题C(i,j)得值,考虑从{ri,…,rj}中选择一个记录rk作为二叉查找树得根结点,可以得到如下关系:因此,得到如下动态规划函数:C(i,i-1)=0(1≤i≤n+1)(式6、