矩阵乘积

Description

Input

n表示矩阵的个数(<=100)
n+1个数,表示矩阵(<=100)

Output

最小的乘法次数

Sample Input

5
5 10 4 6 10 2

Sample Output

348

解题思路

这道题的动态转移方程:
c [ j ] [ i ] = m i n ( c [ j ] [ i ] , c [ j + k ] [ i − k ] + c [ j ] [ k ] + a [ j ] ∗ a [ i + j ] ∗ a [ j + k ] ) ; c[j][i]=min(c[j][i],c[j+k][i-k]+c[j][k]+a[j]*a[i+j]*a[j+k]); c[j][i]=min(c[j][i],c[j+k][i−k]+c[j][k]+a[j]∗a[i+j]∗a[j+k]);
i为开头，j为末尾，k为中间隔开的位置。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[102],b[102],f[102][102],t;
int main()
{
   
    cin>>n;
    for(long long i=1;i<=n+1;i++) cin>>a[i];
    for(long long i=2;i<=n;i++)
     for(long long j=1;j<=n-i+1;j++)
     {
   
        f[j][i]=0x7f7f7f7f;//赋初值
        for(long long k=1;k<i;k++)
		 f[j][i]=min(f[j][i],f[j+k][i-k]+f[j][k]+a[j]*a[i+j]*a[j+k]);//动态转移方程
     }
    cout<<f[1][n];
    return 0;
}

谢谢阅读，如有疑惑或发现作者错误请在评论区留言。