CLength2(i-1,j);returna1>a2?a1:a2;}}}publicstaticvoidmain(String[]args){char[]A={'g','f','d','a','s','d','a','c'};char[] B={'g','c','f','a','t','0','c','c'};LSClsc=newLSC(A,B);System.out.println(lsc.LSCLength2(7,7));}}9、记矩阵连乘积。确定计算A[1:n]的最优计算次序,使得所需数乘的次数最少。1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解,即最优子结构性质。2、该问题具备子问题的重叠性质。3、说明采用动态规划方法可以解决该问题。4、设计该算法,分析算法的复杂性。答:计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n]当i=j时,A[i:j]=Ai,无需计算,因此,m[i,j]=0,i=1,2,…,n当i<j时,利用最优子结构性质计算m[i,j].设A[i:j]的最优次序在Ak和Ak+1之间断开,则m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj其中Ai的维数为pi-1×pjk的位置只有j-i种可能,{i,i+1,…,j-1},其中使计算量最小的那个位置为最优解,数乘次数m[i,j]最小值为问题的最优值可以递归地定义m[i,j]为:m[i,j]={min{m[i,k]+0m[k+1,j]+pi-1pkpj}i=ji<j}将最优值m[ij]对应的断开位置记为s[ij],则可递归的由s[ij]构造出相应的最优解对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此,不同子问题的个数最多只有
全文预览
