计算矩阵连乘积——动态规划

在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：

现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An，最少的乘法次数。

递归公式：

//2.动态规划解决计算矩阵连乘积

#include<stdio.h>

#include<string.h>

#define MaxNum 100

void MatrixChain(int p[MaxNum],int n,int m[MaxNum][MaxNum],int s[MaxNum][MaxNum]);

void traceback(int i,int j,int s[MaxNum][MaxNum]);

int main()

{

      int P[MaxNum];

      int N;

      int r;

      int M[MaxNum][MaxNum];

      int S[MaxNum][MaxNum];

      while(scanf("%d",&N) && N!=0)

      {

             for(r=0;r<=N;r++)

             {

                    scanf("%d",&P[r]);

             }

             MatrixChain(P,N,M,S);

             traceback(1,N,S);

      }

      return 0;

}

void MatrixChain(int p[MaxNum],int n,int m[MaxNum][MaxNum],int s[MaxNum][MaxNum])

{       

      for (int i = 1; i <= n; i++)

      {

             m[i][i] = 0;

      }

    for (int r = 2; r <= n; r++)

      {

             for (int i = 1; i <= n - r+1; i++)

             {

                    int j=i+r-1;

            m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

            s[i][j] = i;

            for (int k = i+1; k < j; k++)

                    {

                           int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

                if (t < m[i][j])

                           {

                                  m[i][j] = t;

                                  s[i][j] = k;

                           }

            }   

             }

      }

}

void traceback(int i,int j,int s[MaxNum][MaxNum])

{

   if(i==j)

         printf("A%d",i);

   else if (i==j-1)

         printf("(A%dA%d)",i,j);

   else

   {

         printf("(");

         traceback(i,s[i][j],s);

         traceback(s[i][j]+1,j,s);

         printf(")");

      }

}