Very easily understandable c++ code


#1

int rec(vector &A, int start, int end, int tmp, vector<vector> &dp){
if (start==end) return 0;

if (tmp==0){
    if (dp[start+1][end]==-1)  dp[start+1][end] = rec(A,start+1,end,1,dp);
    if (dp[start][end-1]==-1)  dp[start][end-1] = rec(A,start,end-1,1,dp);
    dp[start][end] = max(A[start] + dp[start+1][end], A[end] + dp[start][end-1]);
    return dp[start][end];
}
else{
    if (dp[start+1][end]==-1)  dp[start+1][end] = rec(A,start+1,end,0,dp);
    if (dp[start][end-1]==-1)  dp[start][end-1] = rec(A,start,end-1,0,dp);
    dp[start][end] =  min(0 + dp[start+1][end], 0 + dp[start][end-1]);
    return dp[start][end];
}

}

int Solution::maxcoin(vector &A) {
int n = A.size();
vector<vector> dp(n,vector(n,-1));
return rec(A,0,n-1,0,dp);
}