矩阵连乘的动态规划（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。解答:我们按照动态规划的几个步骤来分析：（1）找出最优解的性质，刻画其特征结构对于矩阵连乘问题，最优解就是找到一种计算顺序，使得计算次数最少。令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。将矩阵连乘积简记为A[i:j]，这里i<=j.假设这个最优解在第k处断开，i<=k<j，则A[i:j]是最优的，那么A[i,k]和A[k+1:j]也是相应矩阵连乘的最优解。可以用反证法证明之。这就是最优子结构，也是用动态规划法解题的重要特征之一。（2）建立递归关系设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。当i=j时，A[i,j]=Ai,m[i,j]=0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0)当i<j时，m[i,j]=min{m[i,k]+m[k+1,j]+pi-1*pk*pj},其中i<=k<j(相当于对i~j这段,把它分成2段,看哪种分法乘的次数最少,如A1,A2,A3,A4,则有3种分法:{A1}{A2A3A4}、{A1A2}{A3A4}、{A1A2A3}{A4},其中{}表示其内部是最优解,如{A1A2A3}表示是A1A2A3的最优解),也即：（3）计算最优值对于1≤i≤j≤n不同的有序对(i,j)对于不同的子问题，因此不同子问题的个数最多只有o(n*n).但是若采用递归求解的话，许多子问题将被重复求解，所以子问题被重复求解，这也是适合用动态规划法解题的主要特征之一。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。下面给出动态规划求解最优值的代码：//也是要枚举求到的，但是如果我们之前先记录下这些小规模的情况，当求大规模的时候，直接提取就行了，因此体现了记忆搜索的说法voidMatrixChain(int*p,intn,int**m,int**s){//m是最优值,s是最优值的断开点的索引,n为题目所给的矩阵的个数(下面例子中)//矩阵段长度为1,则m[][]中对角线的值为0,表示只有一个矩阵,没有相乘的.for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++){//r表示矩阵的长度(2,3…逐渐变长)for(inti=1;i<=n-r+1;i++){//从第i个矩阵Ai开始,长度为r,则矩阵段为(Ai~Aj)intj=i+r-1;//当前矩阵段(Ai~Aj)的起始为Ai,尾为Aj//求(Ai~Aj)中最小的,其实k应该从i开始，但些处先记录第一个值，k从i+1开始，这样也可以。//例如对(A2~A4),则i=2,j=4,下面一行的m[2][4]=m[3][4]+p[1]*p[2]*p[4],即A2(A3A4)m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//记录断开点的索引//循环求出(Ai~Aj)中的最小数乘次数for(intk=i+1;k<j;k++){//将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k+1][j]),//再加上左右2部分最后相乘的次数(p[i-1]*p[k]*p[j])intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;//保存最小的,即最优的结果}//if}//k}//i}//r}//MatrixChain上面代码中后面的k也相当于是从i到j-1递增的,只是单独把第一个(k=i)提了出来.5102025}:⨯3515⨯对于p={30计算顺序为：对上例,共6个矩阵(A1~A6),n=6,当r=3时,r循环里面的是3个矩阵的最优解,i从1->4,即求的是(A1A2A3),(A2A3A4),(A3A4A5),(A4A5A6)这4个矩阵段(长度为3)的最优解.当i=2时(A2A3A4)的最优解为{A2(A3A4),(A2A3)A4}的较小值。•矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后