xmu 1029

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.条件 iM[i:j]=min { M[i:k]+M[k+1][j]+p(i-1)*p(k)*p(j) } 其中 i<=k2.条件 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 ;
}