算法设计实验(共3页).doc

精选优质文档-倾情为你奉上实验三：动态规划法【实验目的】应用动态规划算法思想求解矩阵连乘的顺序问题。【实验要求】应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透Ai,j，A1,n=A1,k Ak+1,n，mij，sij各式所表达的含义并正确加以应用。mij的递归定义： 0 （ i=j ）mij= minmik mk+1j+ni-1nknj （ ij）要求完成：算法描述写出程序代码完成调试进行过程与结果分析。【实验性质】验证性实验。【实验内容】对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2， ，An的连乘积，它们的维数分别为d0,d1,dn