算法导论上的题目，用动态规划算法解矩阵链乘法问题需要时间为O(n^3),空间为O(n^2)。

     问题描述：

　　给定n个矩阵构成的一个链（A1*A2*A3……*An），其中i=1,2,……n,矩阵Ai的维数为p(i-1)*p(i),对于乘积A1*A2*A3……*An以一种最小化标量乘法次数的方式进行加括号。

/*************************************************************************    > File Name: maxtrix_chain.c    > Author: He Xingjie    > Mail: gxmshxj@163.com    > Created Time: 2014年05月18日 星期日 11时31分33秒    > Description:动态规划求矩阵链乘法的乘数最小  ************************************************************************/#include
     
      #define MAX 50typedef struct{    int a;    int b;}Matrix;Matrix matrix[MAX];int m[MAX][MAX];int s[MAX][MAX];void Input(int *len){    int i;    FILE *filp;    filp = fopen("in.txt","r");    if (filp == NULL)        printf("file ope failed!\n");    fscanf(filp, "%d", len);        /*scanf("%d", len);*/    for(i = 0; i < *len; i++)    {        /*scanf("%d%d", &matrix[i].a, &matrix[i].b);*/        fscanf(filp, "%d%d", &matrix[i].a, &matrix[i].b);    }}int MatrixChain(int len){    int l, i, j, k;    int tmp;    for (i = 0; i < len; i++)    {        for (j = i; j < len; j++)        {            if (i == j)                m[i][i] = 0;            else                m[i][j] = 99999999;            s[i][j] = 0;        }    }    for (l = 2; l <= len; l++)    {        for (i = 0; i < len-l+1; i++)        {            j = i+l-1;            for (k = i; k < j; k++)            {                tmp = m[i][k] + m[k+1][j] +                    matrix[i].a * matrix[k].b * matrix[j].b;                if (tmp < m[i][j])                {                    m[i][j] = tmp;                    s[i][j] = k;                }            }        }    }        return m[0][len-1];    }void PrintResult(int i, int j){    if (i == j)        printf("A%d", i);    else    {        printf("(");        PrintResult(i, s[i][j]);        PrintResult(s[i][j]+1, j);        printf(")");    }}void PrintM(int len){    int i, j;    for (i = 0; i < len; i++)    {        for (j = 0; j < len; j++)        {            printf("%d ",m[i][j]);        }        printf("\n");    }}int main(void){    int n, ret;    Input(&n);    printf("n:%d\n", n);    ret = MatrixChain(n);     printf("result:%d\n", ret);    printf("k:%d.\n", s[0][n-1]);    PrintM(n);    PrintResult(0, n-1);    return 0;}