算法设计与分析 王红梅 第二版 第6章_动态规划教程文件.ppt

第6章 动态规划Dynamic Programming;*;*;*;*;*;*;*;*;*;*;*;*;一个简单的例子——数塔问题;数塔问题——想法;求解初始子问题：底层的每个数字可看作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.1 maxAdd[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数组确定每一层决策的列下标，输出路径信息；;数塔问题——算法;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;问题描述：在数字序列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++语言描述的算法。;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*; 设{r1, r2, …, rn}是n个记录的集合，其查找概率分别是{p1, p2, …, pn}，最优二叉查找树（Optimal Binary Search Trees）是以这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.17） C(i, i)=pi (1≤i≤n) （式6.18） C(i, j)=min{C(i, k-1)+C(k+1, j)+ } (1≤i≤j≤n,i≤k≤j) （式6.19） 设一个二维表C[n+1][n+1]，其中C[i][j]表示二叉查找树T(i, j)的平均比较次数。注意到在式6.19中，当k=1时，求C[i][j]需要用到C[i][0]，当k=n时，求C[i][j]需要用到C[n+1][j]，所以，二维表C[n+1][n+1]行下标的范围为1～n+1，列下标的范围为0～n。 为在求出由{r1, r2, …, rn}构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表R[n+1][n+1]，其下标范围与二维