C++ Solution using Top down approach


#1
int driver(vector<int>& nums, int i, int j, vector<vector<int>>& dp){
    if(i==j){
        dp[i][j] = nums[i];
        return dp[i][j];
    }
    if(i+1 == j){
        dp[i][j] = max(nums[i], nums[j]);
        return dp[i][j];
    }
    if(dp[i][j]==-1)
        dp[i][j] = max(
            (nums[i] + min(driver(nums, i+2, j, dp), driver(nums, i+1, j-1, dp))),
            (nums[j] + min(driver(nums, i+1, j-1, dp), driver(nums, i, j-2, dp)))
        );
    return dp[i][j];
}

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