矩阵连成问题动态规划

   1. #include<iostream>  
   2. using namespace std;  
   3. const int N=20;  
   4.   
   5. int  MaTrixChain (int n, int *p, int m[N][N], int s[N][N])  
   6. {  
   7.     for(int i=1;i<=n;i++){  
   8.         m[0][i]=0;  s[0][i]=0;  
   9.         m[i][0]=0;  s[i][0]=0;  
  10.         m[i][i]=0;  s[i][i]=0;  
  11.         m[0][0]=0;  s[0][0]=0;  
  12.     }  
  13.     for(int r=2;r<=n;r++)  
  14.         for(int i=1;i<=n-r+1;i++){  
  15.             int j=i+r-1;  
  16.             m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];  
  17.             s[i][j]=i;  
  18.             m[j][i]=0; s[j][i]=0;  
  19.             for(int k=i+1;k<j;k++){  
  20.                 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];  
  21.                 if (t<m[i][j]){  
  22.                     m[i][j]=t;  
  23.                     s[i][j]=k;  
  24.                 }  
  25.             }  
  26.               
  27.     }     
  28.     return m[1][n];  
  29. }  
  30.