``````//dfs
#include<bits/stdc++.h>

#define LL long long
using namespace std;

int a[105];
int dp[105][105];

int dfs(int L, int R)
{
if(dp[L][R])
{
return dp[L][R];
}
if(R-L<2)
{
return 0;
}
if(R-L==2)
{
return dp[L][R]=a[L]*a[L+1]*a[R];
}
dp[L][R]=(1<<31)-1;
for(int k=L+1;k<=R-1;k++)
{
dp[L][R]=min(dp[L][R], dfs(L, k)+dfs(k, R)+a[L]*a[k]*a[R]);
}

return dp[L][R];
}

int main()
{
int n;
memset(dp, 0, sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
cout<<dfs(1, n)<<endl;

return 0;
}
``````
``````//递推
#include<bits/stdc++.h>

#define LL long long
using namespace std;

int a[105];
int dp[105][105];

int dfs(int n)
{
for(int Len=3;Len<=n;Len++)
{
for(int L=1;L+Len-1<=n;L++)
{
int R=L+Len-1;
dp[L][R]=(1<<31)-1;
for(int k=L+1;k<=R-1;k++)
{
dp[L][R]=min(dp[L][R], dp[L][k]+dp[k][R]+a[L]*a[k]*a[R]);
}
}
}

return dp[1][n];
}

int main()
{
int n;
memset(dp, 0, sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
cout<<dfs(n)<<endl;

return 0;
}
``````