Easy Recursion with memoization


#1

int dp[501][501];
int solve(int i,int j,vector A)
{
if(i+1==j)
return max(A[i],A[j]);
if(i==j)
return A[i];
if(dp[i][j]!=-1)
return dp[i][j];

return dp[i][j]=max(A[i]+min(solve(i+2,j,A),solve(i+1,j-1,A)),A[j]+min(solve(i,j-2,A),solve(i+1,j-1,A)));

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


#3

bro solution is damn sweet but i couldn’t understand the intiution here,help me plese


#4

We can do with player-wise too as the solution suggested.
Here is a better explanation of the above recursion.