Easy CPP Coin solution using DP


#1

Approach : Maximize amount of money with respect to you and minimize it with respect to opponent. You and opponent both don’t know which coin to pick (leftmost or rightmost). Therefore, you have to include both the possibilities in the recursion. Let say you pick the left most coin from n coins. Now the opponent will pick another coin from the extreme ends of the remaining (n-1) coins such that you get minimum final money.

Solution :

int solve(int i, int j, vector &A, vector<vector> &M){

if(i==j-1)
    return max(A[i],A[j]);
    
int t1 = (M[i+2][j]==-1)?solve(i+2,j,A,M):M[i+2][j];
int t2 = (M[i+1][j-1]==-1)?solve(i+1,j-1,A,M):M[i+1][j-1];
int t3 = (M[i][j-2]==-1)?solve(i,j-2,A,M):M[i][j-2];

M[i][j] = max(A[i]+min(t1,t2), A[j]+min(t2,t3));

return M[i][j];

}

int Solution::maxcoin(vector &A) {

int n = A.size();
vector<vector<int>> M(n,vector<int>(n,-1));
return solve(0,n-1,A,M);

}