Code Starts Here:
#include<stdio.h>
#include<limits.h>
#include<string.h>
int t[1001][1001];
int solve(int arr[], int i, int j)
{
if(i>=j)
{
return 0;
}
if(t[i][j]!=-1)
{
return t[i][j];
}
int min=INT_MAX;
for(int k=i;k<=j-1;k++)
{
int tempans=solve(arr,i,k)+(arr,k+1,j)+arr[i-1]*arr[k]*arr[j];
if(tempans<min)
{
min=tempans;
}
}
return t[i][j]=min;
}
int main()
{
memset(t, -1, sizeof(t));
int arr[]={10,20,30,40};
int n=4;
int ans=solve(arr,1,n-1);
printf ("%d", ans);
return 0;
}
Output:
/tmp/PZ3u5lGqYK.o
8003