3d dp using memoization


#1

// dp array initialized to -1
// return rec(0,0,A.size()-1,a,dp);
// a: input array
// player: 0,1
// s: start
//e : end
private int rec(int player, int s, int e, int[] a,int[][][] dp) {
if(s>e)
return 0;
if(dp[player][s][e]!=-1)
return dp[player][s][e];
if(player==0){
dp[player][s][e] = Integer.max(a[s]+rec(1,s+1,e,a,dp),a[e]+rec(1,s,e-1,a,dp));
}else {
dp[player][s][e] = Integer.min(rec(0,s+1,e,a,dp),rec(0,s,e-1,a,dp));
}
return dp[player][s][e];
}