題目：

拿到這道題，我們首先要知道矩陣相乘的規則和過程，具體的乘法過程如下:

要求A的列數=B的行數，并且結果的C矩陣的元素值滿足如下關系：

　　從上式中我們可以求得矩陣C中每個元素值，但是我們這題關心的并不是值，而是相乘的此時，這里我們可以看到求每個元素，需要m個乘積的和，這樣的話，求取完整的矩陣C需要進行l*m*m次相乘。同時由于相鄰矩陣滿足前一個列數等于后一個行數的關系，這樣，我們把每個矩陣行列數保存在數組p中，并且相鄰矩陣的相等行列書只存儲一次，這樣的話，對于矩陣M[i](i=1,2,3,.;.....n)，其是p[i-1]行p[i]列的矩陣。

　　確定好上述的數據存儲，接下來考慮本題，如果檢查每種不同的計算順序那么福復雜度高達O(n!),顯然是不靠譜的，這樣我們可不可以考慮使用動態規劃呢？

　　答案是可以的，我們對于一個大矩陣M[i]*M[i+1]*...*M[j],我們不考慮過多，只想在得到這個矩陣的前一步乘積的情況，有哪些情況呢？比如對于M1*M2*M3*M4*M5,顯然的我們有以下幾種情況，并由此獲得完整的M1*M2*M3*M4*M5的公式:

     1.(M1)*(M2*M3*M4*M5)的次數 =(M1)的次數+ (M2*M3*M4*M5)的次數+p[0]*p[1]*p[5]                     

     2.(M1*M2)*(M3*M4*M5)的次數=(M1*M2)的次數+(M3*M4*M5)的次數+p[0]*p[2]*p[5]

     3.(M1*M2*M3)*(M4*M5)的次數=(M1*M2*M3)的次數+(M4*M5)的次數+p[0]*p[3]*p[5]

     4.(M1*M2*M3*M4)*(M5)的次數=(M1*M2*M3*M4)的次數+(M5)的次數+p[0]*p[4]*p[5]

其中單個矩陣相乘的次數顯然為0,我們再取其中求得最小的次數作為最終M1*M2*M3*M4*M5最小鏈乘次數.這樣的話，我們其實就可以很簡單的獲得動態規劃下數組的意義和遞推關系式,dp[i][j];表示下標從i~j的這部分矩陣的最小鏈乘次數,其中矩陣下標從1到n，遞推關系式如下:

dp[i][j]=0                                                                                                                (i=j)

           =min{dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]} (其中i<=m<=j)                     　　  (i<j)

這樣就和容易得到下面得解題代碼:

#include<iostream>#include<algorithm>using namespace std;#define Max_N 100+1int p[Max_N];                //存放各個矩陣的行列數 ,第i個矩陣大小為p[i-1]*p[i] int dp[Max_N][Max_N];         //矩陣下標從1~n,dp[i][j]表示下標從i~j的這部分矩陣的最小鏈乘次數 int main(){	int n=6;	cin>>n;		for(int i=1;i<=n;i++)	{		cin>>p[i-1]>>p[i];		dp[i][i]=0;	}        //int p[]={30,35,15,5,10,20,25};      //測試使用 	//cout<<endl;	for(int l=2;l<=n;l++)	{		for(int i=1;i<=n-l+1;i++)		{			int j=i+l-1;			dp[i][j]=999999999;		    for(int k=i;k<j;k++) 		    {   //測試使用 		    	//cout<<"dp["<<i<<"]["<<k<<"]:"<<dp[i][k]<<"-";				    //cout<<"dp["<<k+1<<"]["<<j<<"]:"<<dp[k+1][j]<<"-"; 			    //cout<<p[i-1]*p[k]*p[j]<<endl;		    	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);		    	//cout<<"dp["<<i<<"]["<<j<<"]:"<<dp[i][j]<<endl;		    }		  	//cout<<"------------"<<endl;		}	}	cout<<dp[1][n]<<endl;	return 0;}　　但是到這并不結束，下面我想說的是在解題時我的一個錯誤，并分析給大家，以此借鑒:接下來是我的源碼:
#include<iostream>#include<algorithm>               //注意，該方法是錯誤方法 using namespace std;#define Max_N 100+1//int p[Max_N];                //存放各個矩陣的行列數 ,第i個矩陣大小為p[i-1]*p[i] int dp[Max_N][Max_N];         //矩陣下標從1~n,dp[i][j]表示下標從i~j的這部分矩陣的最小鏈乘次數 int main(){	int n=6;	//cin>>n;		for(int i=1;i<=n;i++)	{		//cin>>p[i-1]>>p[i];		dp[i][i]=0;	}        int p[]={30,35,15,5,10,20,25};	for(int i=0;i<=n;i++)	{		cout<<p[i]<<" ";	}	cout<<endl;		for(int i=1;i<=n;i++)	{		for(int j=i+1;j<=n;j++)		{		  	dp[i][j]=99999999;		  	for(int mid=i;mid<j;mid++)       //分成兩個矩陣相乘,i~k和k+1~j 		  	{    //下標i~k的矩陣相乘結果為大小為p[i-1]*p[mid]的矩陣 		  	    //下標k+1~j的矩陣相乘結果為大小為p[mid]*p[j]的矩陣				  //最后兩者矩陣相乘，鏈乘次數為p[i-1]*p[mid]*p[j] 			  //cout<<"dp["<<i<<"]["<<mid<<"]:"<<dp[i][mid]<<"-";				  //cout<<"dp["<<mid+1<<"]["<<j<<"]:"<<dp[mid+1][j]<<"-"; 			  //cout<<p[i-1]*p[mid]*p[j]<<endl;		  	  dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid+1][j]+p[i-1]*p[mid]*p[j]);		  	  //cout<<"dp["<<i<<"]["<<j<<"]:"<<dp[i][j]<<endl;		  	}		  	//cout<<"------------"<<endl;		}	}		for(int i=1;i<=n;i++)	{		for(int j=i;j<=n;j++)		{			cout<<"dp["<<i<<"]["<<j<<"]:"<<dp[i][j]<<endl;		}	}	cout<<dp[1][n]<<endl;	return 0;}　　我將示例中的測試案例寫在了程序中，便于每次的調試。上述代碼的問題就在于其循環時的變量范圍，雖然說兩種代碼最終都保證dp[i][j]中的下標范圍從1變化到n,但是第二種的方法就錯在一下:
   　 該方法的作物之處就在于i,j下標是不斷依次增大的，這樣的話在進行下面一句話: 
dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid+1][j]+p[i-1]*p[mid]*p[j]) 時， 在 dp[mid+1][j]中mid+1>i的情況下，用 dp[mid+1][j]來求dp[i][j]，相當于用之后遍歷到的來求之前的數據，這樣在未遍歷到dp[mid+1][j]時，其值恒為0,也就是說從mid+1到j矩陣鏈乘次數為0,這樣顯然是不可能的。
　　所以為了避免這種情況，首先要想到對于多個矩陣的相乘，其肯定是由其小部分的矩陣鏈乘結果得到的，那么就不能按照下標從小到大順序遍歷，那么就應該用下標范圍的長度來作為遍歷，也就是說先遍歷完短范圍的矩陣鏈乘結果，再得到大范圍鏈乘結果，拋開一句，這里之所以不能用i,j下標作為遍歷標準，就是因為其求結果的時候，并不是說先求小坐標的矩陣，而是先求小范圍，也就是長度小的范圍內，矩陣的鏈乘結果，比如，應該先求 M5*M6*M7,之后再去求M2*M3*...M7,其實就是因為后者的求取需要其一部分矩陣相乘的結果 。
　　　其實這題就告訴我們，動態規劃解題時，我們要找準遞推式中前后變量的范圍，并在保證后者求出結果后再進行遞推，這樣就要求我們在保證動態數組變量范圍不變的情況下，找到正確的下標變化過程。
PS:看書，解題越多，并且感悟越多，對于提升能力肯定是有幫助的，不能只是機械地敲書上的代碼~