2618: 动态规划-矩阵连乘积
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：4
提交：4
正确率：100.00% 命题人：
题目描述
给定 $n$（$1\lt n \le 9$）个矩阵{$A$, $A_2$, …, $A_n$}，其中 $A_i$ 与 $A_{i+1}$ 是可乘的，$i=1,…,n$。要求找到一个计算次序使得求 $n$ 个矩阵连乘积 $A_1$, $A_2$, …, $A_n$ 的数乘次数最少。 例如：如果有 $3$ 个矩阵，第 $1$ 个矩阵的行数和列数分别为 $1$ 和 $2$，第 $2$ 个矩阵的行数和列数分别为 $2$ 和 $3$，第 $3$ 个矩阵的行数和列数分别为 $3$ 和 $4$；如果先计算第 $1$ 个矩阵和第 $2$ 个矩阵的积（数乘次数为 $6=1 \times 2 \times 3$），然后再计算刚得到的结果矩阵( $1$ 行 $3$ 列)与第 $3$ 个矩阵的积（数乘次数为 $12=1 \times 3 \times 4$ ），总数乘的结果为 $18$；如果先计算第 $2$ 个矩阵和第 $3$ 个矩阵的积（数乘次数为 $24=2 \times 3 \times 4$），然后再计算第 $1$ 个矩阵与刚得到的结果矩阵（$2$ 行 $4$ 列）的积（数乘次数为 $8=1 \times 2 \times4 $ ），总数乘的结果为 $32$。因为 $3$ 个矩阵的连乘积的计算方法只有上面两种情况，故最少的数乘次数为 $18$。
测试代码 复制
#include <stdio.h>
int m[11][11]; // 下标为0的单元“不存储”有效数据
int p[11]; // 注意：下标为0的单元“存储”有效数据
void MatrixChain(int p[],int n)
{
for(int i=1;i<=n;i++) m[i][i]=0; //初始化第1条对角线（主对角线）
for(int r=2;r<=n;r++) //分别计算第r(此处没有使用变量p的原因是p已经作为形式参数了)条对角线上的值
{
for(int i=1;i<=n-r+1;i++)
{
}
}
}
int main(void)
{
int i,n,result;
scanf("%d",&n);
for(i=0;i<=n;i++) scanf("%d",&p[i]);
MatrixChain(p,n);
printf("%d\n",m[1][n]);
return 0;
}输入格式
第一行输入一个整数，表示有n个矩阵相乘
第二行输入n+1个整数，分别表示n个矩阵的行和列数。注意，相邻两个矩阵相乘的条件是前者的列数与后者的行数相等，故输入数据时省略了一个整数。
第二行输入n+1个整数，分别表示n个矩阵的行和列数。注意，相邻两个矩阵相乘的条件是前者的列数与后者的行数相等，故输入数据时省略了一个整数。
输出格式
第一行输出最小的数乘次数。
输入样例 复制
3
1 2 3 4输出样例 复制
18提示
算法设计思路：先写出计算m[i][j]值的递归式（与租用游艇问题非常相似），然后根据递归式设计动态规划算法。
如果是4个矩阵，下标分别是1，2，3，4，5，则结果应该是什么？
如果是4个矩阵，下标分别是1，2，3，4，5，则结果应该是什么？