Find maximum number of coins that can be collected in give coins matrix and i can move either right or down from cell.

// Maximum no. of coins 

// int[][] in= {{5,2,8},{10,6,12},{11,5,3}};

// output 36

 public static int maxAmount(int[][] in)
 {
  int row = in.length;
  int col = in[0].length;
  
  //int[][] buf = new int[row][col];
  
  return maxAmountRecUtil(in, row-1, col-1);
  
  //return maxAmountUtil(in, buf, row-1, col-1);
 }
 


// Recursive solution

 private static int maxAmountRecUtil(int[][] in, int i, int j)
 {
  if(i<0 || j<0) return -1;
  
  if(i == 0 && j == 0) return in[i][j];
  
  if(i == 0) return  maxAmountRecUtil(in, i, j-1) + in[i][j];
  
  if(j == 0) return  maxAmountRecUtil(in, i-1, j) + in[i][j];
  
  return  max(maxAmountRecUtil(in, i-1, j), maxAmountRecUtil(in, i, j-1)) + in[i][j];
  
 }
 

// Recursion + Extra memory 
  
 public static int maxAmountUtil(int[][] in, int[][] buf, int i, int j)
 {
  if(i<0 || j<0) return -1;
  
  if(i == 0 && j == 0) buf[i][j] = in[i][j];
  
  if(buf[i][j] != 0) return buf[i][j];
  
  if(i == 0) buf[i][j] =  maxAmountUtil(in, buf, i, j-1) + in[i][j];
  
  if(j == 0) buf[i][j] =  maxAmountUtil(in, buf, i-1, j) + in[i][j];
  
  buf[i][j] =  max(maxAmountUtil(in, buf, i-1, j), maxAmountUtil(in, buf, i, j-1)) + in[i][j];
  
  return buf[i][j];
 }
 

// Dynamic programming 

 public static int maxAmountDP(int[][] in, int[][] buf, int r, int c)
 {
  if(r == 0 && c == 0) buf[0][0] = in[0][0];
  
  for(int j = 1; j <= c; j++)
   buf[0][j] = in[0][j] + buf[0][j-1];
  
  for(int i = 1; i <= r; i++)
   buf[i][0] = in[i][0] + buf[i-1][0];
  
  for(int i = 1; i<=r; i++)
  {
   for(int j=1; j<= c; j++)
   {
    buf[i][j] = max(buf[i-1][j], buf[i][j-1]) + in[i][j];
   }
  }
  return buf[r][c];
 }
 

 private static int max(int m1, int m2) {
  return (m1>m2)?m1:m2;
 }

// Main method

 public static void main(String args[])
 {

  int[][] arr = {{5,2,8},{10,6,12},{11,5,3}};
  int row = arr.length;
  int col = arr[0].length;
  int[][] buf1 = new int[row][col];
                int[][] buf2 = new int[row][col];
  
  long time = System.nanoTime();
  System.out.println(maxAmount(arr));
  System.out.println("Time1: "+(System.nanoTime() - time));
  
  long time2 = System.nanoTime();
  System.out.println(maxAmountUtil(arr, buf1, row-1, col-1));
  System.out.println("Time2: "+(System.nanoTime() - time2));
  
  
  long time3 = System.nanoTime();
  System.out.println(maxAmountDP(arr, buf2, row-1, col-1));
  System.out.println("Time3: "+(System.nanoTime() - time3));
         }