My Solutions ( recursion+memoization ) best to learn dp


#1

int dp[505][505];
int helper(vector arr,int si,int ei,int dp[505][505])
{
if(dp[si][ei]!=-1){return dp[si][ei];}
if(si>ei){ dp[si][ei]=0; return 0;}
if(si==ei){ dp[si][ei]=arr[si]; return arr[si];}

int fans1=0,fans2=0;


fans1=arr[si];
int sec=helper(arr,si+2,ei,dp);
int sec2=helper(arr,si+1,ei-1,dp);
int ans1=fans1+min(sec,sec2);


fans2=arr[ei];
sec=helper(arr,si+1,ei-1,dp);
sec2=helper(arr,si,ei-2,dp);
int ans2=fans2+min(sec,sec2);
dp[si][ei]=max(ans1,ans2);
return dp[si][ei];

}
int Solution::maxcoin(vector &A) {

memset(dp,-1,sizeof(dp));
return helper(A,0,A.size()-1,dp);

}