1 #include
     
       2 #include
      
        3 #define MAXN 1000000 4 void Matrix_Chain_Order(int * p, int * s, int N) 5 { 6        int n = N - 1; 7        int m[N][N]; 8        for(int i = 1; i <= n; i++) 9        {10              m[i][i] = 0;          11        }   12        for(int l = 2; l <= n; l++) /*l是链的长度*/13        {14                for(int i = 1; i <= n - l + 1; i++)15                {16                     int j = i + l - 1;17                     m[i][j] = MAXN;       18                     int q; 19                     for(int k = i; k <= j - 1; k++)20                     {21                          q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];22                          if(q < m[i][j])23                          {24                               m[i][j] = q;25                               *(s + i * N + j) = k;     26                          }           27                     }     28                }             29        }      30 }31 32 void Print_Optimal_Parens(int * s, int i, int j, int N)33 {34      if(i == j)35      {36           printf("A%d",i);     37      }     38      else39      {40          printf("(");41          Print_Optimal_Parens((int *)s, i, *(s + i * N + j), N);42          Print_Optimal_Parens((int *)s,  *(s + i * N + j)+1, j, N);43          printf(")");    44      }45 }46 47 int main()48 {49     int P[7] = {
   30,35,15,5,10,20,25};50     int S[7][7];51     Matrix_Chain_Order(P,(int *)S,7);52     Print_Optimal_Parens((int *)S,1,6,7);53     system("pause");54     return 0;    55 }