给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：

（ 1 ）单个矩阵是完全加括号的；

（ 2 ）矩阵连乘积 A 是完全加括号的，则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A= （ BC ）。

分析：

1. 矩阵连乘的条件：第一个矩阵的列等于第二个矩阵的行，此时两个矩阵是可乘的；

2. 多个矩阵连乘的结果矩阵，其行等于第一个矩阵的行和其列等于最后一个矩阵的列。

3.两个矩阵相乘的计算量：

例如：A（4*2），B（2*5） 可知总执行次数为：4×2×5=40

所以矩阵A m*n和B n*k的乘法运算次数为：m*n*k；

1. 子问题的拆分，在（AiAi+1……Aj）中，先选择一个矩阵Ak，这样的话就将一个大矩阵拆分为两个小矩阵;假设在第k位置上找到最优解，则问题变成了两个子问题：（AiAi+1……Ak），（Ak+1……Aj）；用m[i][j]表示矩阵连乘的最优值，那么两个子问题对应的最优值变成m[i][k],m[k+1][j]; 
2. 矩阵连乘最优值递归式：

#include <stdio.h>
#define N 100// 定义最大连乘的矩阵个数为 100 个
void matrixChain (int p[],int m[N+1][N+1],int s[N+1][N+1])
/* 用 m[i][j] 二维数组来存储 Ai*......Aj 的最小数乘次数，用 s[i][j] 来存储使 Ai......Aj 获得最小数乘次数对应的断开位置 k ，需要注意的是此处的 N+1 非常关键，虽然只用到的行列下标只从 1 到 N 但是下标 0 对应的元素默认也属于该数组，所以数组的长度就应该为 N+1*/
{
 int n=N;// 定义 m,s 数组的都是 n*n 的，不用行列下标为 0 的元素，但包括在该数组中
 for (int i=1;i<=n;i++)
   m[i][i]=0; /* 将矩阵 m 的对角线位置上元素全部置 0 ，此时应是 r=1 的情况，表示先计算第一层对角线上个元素的值 */
 for (int r=2;r<=n;r++)//r 表示斜对角线的层数，从 2 取到 n
 {
   for (int i=1;i<=n-r+1;i++)//i 表示计算第 r 层斜对角线上第 i 行元素的值
   {
     int j=i+r-1;//j 表示当斜对角线层数为 r ，行下标为 i 时的列下标
     m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];// 计算当断开位置为 i 时对应的数乘次数
     s[i][j]=i;// 断开位置为 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];/* 计算当断开位置 k 为从 i 到 j （不包括 i 和 j ）的所有取值对应的 (Ai*......*Ak)*(Ak+1*.......Aj) 的数乘次数 */
       if (t<m[i][j])
       {
         m[i][j]=t;// 将 Ai*......Aj 的最小数乘次数存入 m[i][j]
         s[i][j]=k;// 将对应的断开位置 k 存入 s[i][j]
       }
     }
   }
 }
}
void traceback (int i,int j,int s[][N+1])// 用递归来实现输出得到最小数乘次数的表达式
{
 if (i==j)
 {
   printf ("A%d",i);
 }
 else
 {
   printf ("(");
 traceback (i,s[i][j],s);
 traceback(s[i][j]+1,j,s);
 printf (")");
 }
}
int main ()
{
 int n;// 用来存储矩阵的个数
 int Q[2*N];/* 用 Q 数组来存储最原始的输入（各矩阵的行和列），主要目的是为了检验这 N 个矩阵是否满足连乘的条件 */
 int p[N+1],flag=1;/* 用 p[i-1],p[i] 数组来存储 A 的阶数， flag 用来判断这 N 个矩阵是否满足连乘 */
 int m[N+1][N+1];//  用 m[i][j] 二维数组来存储 Ai*......Aj 的最小数乘次数
 int s[N+1][N+1];//  用 s[i][j] 来存储使 Ai......Aj 获得最小数乘次数对应的断开位置 k
 printf (" 请输入矩阵的个数（小于 100 ） :");
 scanf ("%d",&n);
 for (int i=0;i<=2*n-1;i++)// 各矩阵的阶数的输入先存入数组 Q 中接受检验
 {
   if (i%2==0)
   {
     printf ("\n");
     printf (" 请输入A%d的 行 :",(i/2)+1);
   }
   else
   {
     printf ("             列:");
   }
 scanf ("%d",&Q[i]);
 }
 for (int i=1;i<=2*n-2;i++)// 矩阵连乘条件的检验
 {
 if (i%2!=0&&Q[i]!=Q[i+1])
   {
     flag=0;
     break;
   }
 }
 for (int j=1;j<=n-1;j++)
 {
     p[j]=Q[2*j];
 }
 if (flag!=0)
 {
 p[0]=Q[0];
 p[n]=Q[2*n-1];
   matrixChain (p,m,s);
   printf (" 式子如下 :\n");
   traceback(1,n,s);
   printf ("\n");
   printf (" 最小数乘次数为 %d\n",m[1][n]);
 }
 else
 {
   printf (" 这 %d 个矩阵不能连乘 !\n",n);
 }
 }

• 实验结果与分析

（1）实验结果

1.输入正确结果的情况

1. 输入有误的情况：
2. 

（2）分析与收获

经过这个对这个程序的了解和深入研究，渐渐理解了动态规划的基本思想。