实验三：动态规划法
【实验目的】
深入理解动态规划算法的算法思想，应用动态规划算法解决实际的算法问题。

【实验性质】
验证性实验。

【实验要求】
对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。

该问题描述为：一般地，考虑矩阵A1，A2，…，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di (1≤i≤n)。

确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。

对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。

按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。

完成测试。

【算法思想及处理过程】
【程序代码】
printf ("\n\n矩阵连乘次数的最优值为:\n");
printf ("-----------------------------------------------\n");
print2 (0, 6-1, s);
printf ("\n-----------------------------------------------\n\n");
return 0;
}
void MatrixChain (int p[], int m[][6], int s[][6], int n)
{
int i, j, k, z, t;
for (i=0; i<n; i++)
{
m[i][i] = 0;
s[i][i] = 0;
}
for (z=2; z<=n; z++)
for (i=0; i<=n-z; i++)
{
j = i + z - 1;
m[i][j] = m[i+1][j] + p[i] * p[i+1] * p[j+1];
s[i][j] = i;
for (k = i+1; k<j; k++)
{
t = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1];
if (t < m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
void print1 (int m[][6], int s[][6],int p[])
{
int i, j;
printf ("\n\n程序所给矩阵如下:\n");
printf ("-----------------------------------------------\n");
for (i=0; i<6; i++)
printf ("A%d 矩阵: %2d X %-2d \n",i+1,p[i], p[i+1]);
printf ("\n\n-----------------------------------------------\n"); printf("矩阵的最少计算次数为：%d\n", m[0][5]);
printf ("-----------------------------------------------\n");
printf ("\n\n数乘次数: \n");
printf ("-----------------------------------------------\n");
for (i=0; i<6; i++)
{
for (j=0; j<i; j++)
printf (" ");
for (j=i; j<6; j++)
printf ("%-7d", m[i][j]);
printf ("\n");
}
printf ("-----------------------------------------------\n");
printf ("\n\n中间断点: \n");
printf ("-----------------------------------------------\n");
for (i=0; i<6; i++)
{
for (j=0; j<i; j++)
printf (" ");
for (j=i; j<6; j++)
printf ("%-7d", s[i][j]);
printf ("\n");
}
printf ("-----------------------------------------------\n"); }
void print2(int i, int n, int s[][6])
{
if (i == n)
【运行结果】
【算法分析】
函数MatrixChain( )包含三重循环,循环体内的计算量为O(1) , 所以算法的时间复杂度为O(n3) ,算法的空间时间复杂度为O(n3) .
【实验总结】。