Stones Problem

StonesProblem.java

class StonesProblem {
   int[][] stageScore=null;
    public boolean stoneGame(int[] piles) {
      stageScore= new int[piles.length+2][piles.length+2];
      // stoneGameRec(0, piles, true,0,piles.length-1)>0
      return stoneGameBottomUp(piles)>0;
    }
  
    public int stoneGameRec(int sumSoFar, int [] piles, boolean positive, int begin, int end){
      if(stageScore[begin][end]!=0){
        return stageScore[begin][end];
      }
      if(begin < end){
      int first = positive ? piles[begin]: -piles[begin];
      int last= positive ? piles[end]: piles[end];
      int result=-1;  
      if(positive)  {
      result=Math.max(stoneGameRec(sumSoFar+first,piles,!positive, begin+1,end),
                stoneGameRec(sumSoFar+last,piles,!positive,begin,end-1));  
        
      }
      else{
        result=Math.min(stoneGameRec(sumSoFar+first,piles,!positive, begin+1,end),
                stoneGameRec(sumSoFar+last,piles,!positive,begin,end-1));  
      }
      stageScore[begin][end]=result;
      return result;
      }
      else return sumSoFar;
    }
    public int stoneGameBottomUp(int [] piles){
      int N = piles.length;
      for(int k=1; k<=N; k++)  {
        for(int i=0; i+k <= N ;i++){
          int j = i + k -1;
          boolean positive= ((j + i) % 2 == 1);
          if(positive){
            stageScore[i+1][j+1]= Math.max(piles[i]+stageScore[i+2][j+1],piles[j]+stageScore[i+1][j]);
          }
          else{
            stageScore[i+1][j+1]= Math.min(-piles[i]+stageScore[i+2][j+1],-piles[j]+stageScore[i+1][j]);
          }
        }
      }
      System.out.println(stageScore[1][N]);
      return stageScore[1][N];
    }
  
}