|
Description
给定一个有N个矩阵的矩阵链A1A2A3...An，矩Ai的维数为pi-1*pi。我们都知道，使用朴素的矩阵乘法去乘两个维数分别为x,y和y,z的矩阵，所需要的乘法次数为x*y*z。矩阵链乘法问题就是如何对矩阵乘积加括号，使得它们的乘法次数达到最少。
Input
输入的第一行为一个正整数N(1<=N<=200)。表示矩阵的个数。
输入的第二行包含N+1个整数，分别表示pi(0<=i<=N)，其中每个pi在[1,200]范围内。
Output
输出一个整数表示最少要进行的乘法次数。
|
这是个典型的动态规划问题，不过问题难度不大，但从这个题目中慢慢摸索出动态规划题目的一些共性来，而且从很多算法书中都可以找到类似的介绍。
有N个矩阵，A1*A2*A3.....An ,我们求A[1:N]最小，若在n=k处矩阵链断使得A[1:N]最小，则在A[1:k]和A[k:N]这两个子链中他们也是最小的，不然会有更小的A[1:N]，与假设条件A[1:N]最小相矛盾。
我们记从1：N 次数为M[1][N],则有下面的：
M[1][N]=M[1][k]+M[k+1][N]+p(k-1)*p(k)*p(N);
而我们是不知道k的，但k的取值范围被确定了，在[1,N-1]这个区间里。在此我们得到更加一般的情况，
1.条件 i<j ：
M[i:j]=min { M[i:k]+M[k+1][j]+p(i-1)*p(k)*p(j) } 其中 i<=k<j
2.条件 i=j
A[i:i]=Ai，就这一个矩阵，不用相乘。M[i][i]= 0
从上面的简单分析，可以比较简单的写出代码来：(这是逆推的，动态规划经常用到顺推，其实用顺推也可以把代码写出)
|
#include<cstdlib>
#include<iostream>
int m[202][202];
using namespace std ;
int arrayque(int i,int j, int * array)
{
if(i==j) return 0 ;
if(m[i][j]>0) return m[i][j];
int u = array[i-1]*array[i]*array[j]+arrayque(i+1,j,array);
if(i<j)
{
for(int k=i+1;k<j;k++)
{
int temp = arrayque(i,k,array)+arrayque(k+1,j,array)+array[i-1]*array[k]*array[j];
if(temp < u)
u = temp ;
}
m[i][j]=u ;
return m[i][j];
}
}
int main()
{
int number ;
int rezult ;
cin>>number ;
int* array = new int [number+1] ;
int i = 0 ;
while(i<=number)
cin>>array[i++] ;
for(int i=0;i<=number+1;i++)
for(int j=0;j<=number+1;j++)
m[i][j]=0 ;
rezult=arrayque(1,number,array);
cout<<rezult<<endl;
system("pause");
return 0 ;
}
|
