Simple recursive easy to understand solution


#1

int coins(vector&A,int i,int j,int turn,int dp[501][501])
{
if(i>j)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
if(turn==0)
return dp[i][j]=max(A[j]+coins(A,i,j-1,turn^1,dp),A[i]+coins(A,i+1,j,turn^1,dp));
else
return dp[i][j]=min(coins(A,i,j-1,turn^1,dp),coins(A,i+1,j,turn^1,dp));

}
int Solution::maxcoin(vector &A) {
int dp[501][501];
for(int i=0;i<501;i++)
for(int j=0;j<501;j++)
dp[i][j]=-1;
return coins(A,0,A.size()-1,0,dp);
}