题目描述：
-
有若干个矩阵{Ai}，元素都为整数且已知矩阵大小。
如果要计算所有矩阵的乘积A1 * A2 * A3 .. Am，最少要多少次整数乘法？
- 输入
- 第一行一个整数n(n <= 100)，表示一共有n-1个矩阵。
第二行n个整数B1, B2, B3... Bn(Bi <= 100)，第i个数Bi表示第i个矩阵的行数和第i-1个矩阵的列数。
等价地，可以认为第j个矩阵Aj(1 <= j <= n - 1)的行数为Bj，列数为Bj+1。 - 输出
- 一个整数，表示最少所需的乘法次数
- 采用动态规划分析：
- 优化目标是基本运算次数最小化，而这道题关键在于确定一个乘法的次序，相当于在n个矩阵间加括号。如何界定子问题的边界是产生的问题。如果从前向后划分，所产生的子问题只有后边界，但是在计算子问题A1.....j的过程中，我们需要知道子问题A1....i和子问题A(i+1)....j的信息，所以问题需要前后两个边界。用m[i][j]表示乘积Ai....j所用的最小运算次数。假定最后一次相乘发生在Ai.....k和A(k+1).....j之间，那么m[i][j]=min(i≤k<j){m[i][k]+m[k+1][j]+B(i-1)*B(k)*B(j)};
- 下边是代码的c语言实现
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX=;
int m[][MAX];
int dp(int *p,int n){
for(int r=;r<=n;r++){
for(int i=;i<=n-r+;i++){
int j=i+r-;
m[i][j]=m[i+][j]+p[i-]*p[i]*p[j];
for(int k=i+;k<=j-;k++){
int t= m[i][k]+m[k+][j]+p[i-]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
}
}
}
}
return m[][n];
}
int main(){
int n;
scanf("%d",&n);
memset(m,,sizeof(m));
int p[];
for(int i=;i<n;i++){
scanf("%d",p+i);
}
int res=dp(p,n-);
printf("%d\n",res);
return ;
}
算法时间复杂度为O(n3)。