Using MCM concept (Rec+MEMO)


#1

pair<int,int> dp[201][201];
pair<int,int> fun(int i, int j,vector &A)
{
pair<int,int> x;
x.first=0;
x.second=INT_MAX;
if(i>j)
{
return x;
}
if(i==j)
{
x.first=A[i];
x.second=0;
return x;
}
if(dp[i][j].first!=-1)
{
return dp[i][j];
}
int temp;
for(int k=i;k<j;k++)
{
temp=fun(i,k,A).second+fun(k+1,j,A).second+fun(i,k,A).first+fun(k+1,j,A).first;
if(x.second>temp)
{
x.second=temp;
x.first=fun(i,k,A).first+fun(k+1,j,A).first;
}
}
return dp[i][j]=x;
}

int Solution::solve(vector &A) {
memset(dp,-1,sizeof(dp));
return fun(0,A.size()-1,A).second;

}