问题描述：给定n个矩阵（A1,A2,A3.....An}，其中Ai与Ai+1是可乘的，i=1,2,...n-1。考察n个矩阵的连乘积A1A2A3,....An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。加括号的方式决定了整个计算量（指的是乘法调用的次数）。所以自然会提出矩阵连乘积的最优计算次序问题。

    自然，首先想到的是用枚举法，算出每一种加括号情况下的计算量，取最小的情况。工程之庞大可想而知。溯其源，会发现，"枚举“的这种想法是不可避免的，只有所有情况都考虑比较后，才会出现那个最小量乘的结果。普通的枚举导致庞大工程的一个重要因素就是”子问题重复计算“。这里先要明确，什么是矩阵连乘的子问题。

    以A1A2A3A4为例，它的子问题为：A1    A2    A3    A4     A1A2    A2A3     A3A4  A1A2A3   A2A3A4   A1A2A3A4 。你要求A1A2A3A4的最优次序，势必要先求段长为3的子问题的最优次序，而段长为3的子问题是基于段长为2的子问题的基础之上的（这就是一种自底向上的递归）。以此推下去，你很容易会发现两个有意思的现象:第一，假如你已计算出段长为3的子问题的最优次序，那该最优次序下的子问题也是最优的（你可以通过反证法获知）；第二，计算完段长为2的子问题，再计算段长为3的子问题时，你还会用到段长为2的子问题的计算结果，那何不把先前的计算结果进行保存，避免重复计算。

    以下就是动态规划算法解决矩阵连乘问题的相关代码，思想无非就两点：

    第一，自底向上的递归式：    

    需要指出的是：m[i][j]表示Ai.....Aj的最少数乘次数，k表示求解Ai....Aj的子问题最优值时的断开位置，Pi-1PkPj表示AiAi+1.....Ak和Ak+1....Aj相乘时数乘数。

第二，在计算过程中，保存已解决的子问题答案。

#include
    
     using namespace std;void outPut(int i,int j,int **s){	if(i==j)		return;	outPut(i,s[i][j],s);	outPut(s[i][j]+1,j,s);	cout<<"Multiply A "<
     <<","<
      
       >num;	dimension=new int[num+1];     //矩阵维数    mm=new int*[num];	ss=new int*[num];	for(int i=0;i
       
        >dimension[r];	MartrixChain(num,dimension,mm,ss);}
       
      
    

    程序实现并不难，但是还是要交代几点容易犯错的细节：

    1.表示矩阵维数的数组大小：应该是矩阵个数+1，理由......呵呵；

    2.若Ai表示连乘矩阵中第i个矩阵，请你时刻记住，实际上的数组下标是从0开始的;（程序中，我是令i从0开始的）

    这两点都可以通过调试修正，只是如果一开始就能想明白，没必要花这种时间。

    运行结果如下：

    我来解释下运行结果  A  1 , 1  and  A  2 , 2     表示（A1A2）是一个分块的  依次为(A1A2)    (A0(A1A2))    (A3A4)    ((A3A4)A5)    (A0A1A2)(A3A4A5)   综合考虑后，最后加括号的方式为：（（ A0 ( A1 A2 ) ) ( ( A3 A4 ) A5 ) )   。

    最后，来总结下动态规划算法的要素：1.最优子结构的性质     2.重叠子问题性质

    (在此不再赘述，从问题分析中已经体现)。

    特别想交代下的是，我在问题分析中提到”枚举“一词，个人觉得动态规划就是”变相的枚举“，只是它通过小规模的一步步枚举在缩小范围，进而减少重复枚举，能达到这个目的就是基于上述的两个要素，而动态规划能得到正确的答案，则是因为它已经考虑比较了所有可能的情况（这也是解决任何问题所不能避免的,只是有些是隐式比较而已）。

    还有一个非常欠缺的地方：怎么样直接输出加括号的表达式呢？如（（ A0 ( A1 A2 ) ) ( ( A3 A4 ) A5 ) )   。如果无视空间的代价，多开几个数组，用上队列的思想，是可以实现，能不能有更简洁的方法呢？~~~communicating!!!!!!!!

本文转自农夫山泉别墅博客园博客，原文链接：http://www.cnblogs.com/yaowen/p/4476487.html，如需转载请自行联系原作者