矩阵连乘问题

 

Description

   一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵，运算量为n*m*p。
  矩阵乘法满足结合律，A*B*C可以表示成(A*B)*C或者是A*(B*C)，两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时，(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
  现在给出N个矩阵，并输入N+1个数，第i个矩阵是a[i-1]*a[i]

Input

第一行n(n<=100)
第二行n+1个数 

Output

最优的运算量

Sample Input

3
2 3 4 5

Sample Output

64

区间dp

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <sstream>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e5+10;
using namespace std;
 
int a[105];//记录矩阵信息 
int dp[105][105];//dp[i][j]表示矩阵i连乘到j的最优解 
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        scanf("%d",&a[i]);
        if(i!=n+1)
            dp[i][i]=0;
    }
    for(int i=1;i<=n-1;i++)//i为长度 
    {
        for(int j=1;j<=n-i;j++)//j为起始点 
        {
            int t=INF;
            for(int k=j;k<=j+i-1;k++)//k为分割点 
                t=min(t,dp[j][k]+dp[k+1][j+i]+a[j]*a[k+1]*a[j+i+1]);
            dp[j][j+i]=t;
        }
    }
    printf("%d
",dp[1][n]);
    return 0;
}