Coin changing problem + java

// Minimum no. of coins 


// Recursive solution 

 public static int minCoins(int[] coins, int amount)
 {
  if(amount == 0) return 0;
  
  int min = amount; // max coins can equal to amount
  
  for(int i = 0; i < coins.length; i++)
  {
   if(amount - coins[i] >= 0)
   {
    int noOfCoins = minCoins(coins, amount-coins[i]) + 1;
    
    if(noOfCoins < min)
     min = noOfCoins;
   }
  }
  return min;
 }
 

// Recursion + Extra memory

 public static int minCoinsWithBuf(int[] coins, int amount, int[] buf)
 {
  if(amount == 0)
   buf[amount] = 0;
   
  if(buf[amount] != 0) 
   return buf[amount];
  
  
  int min = amount; // max coins can equal to amount
  
  for(int i = 0; i < coins.length; i++)
  {
   if(amount - coins[i] >= 0)
   {
    int noOfCoins = minCoinsWithBuf(coins, amount-coins[i], buf) + 1;
    
    if(noOfCoins < min)
     min = noOfCoins;
   }
  }
  
  buf[amount] = min;
  
  return buf[amount];
 }
 

// DP / Without Recursion + Extra memory
 
 public static int minCoinsDP(int[] coins, int amount, int[] buf)
 {
  if(amount == 0) return 0;
  
  if(amount == 1) return 1;
  
  buf[0] = 0; buf[1] = 1;
  for(int i = 2; i <= amount; i++)
  {
   int min = amount;
   for(int j = 0; j< coins.length; j++)
   {
    if((i-coins[j] >= 0))
    {
     int c = buf[i-coins[j]]+1;
     if(c < min)
      min = c;
    }
   }
   buf[i] = min;
  }
  return buf[amount];
 }
 


// Main method

 public static void main(String args[])
 {
  int amount = 40;
  int[] coins = {1,3,5,7};
  int[] buf1 = new int[amount+1];
  int[] buf2 = new int[amount+1];
  
  
  
  long time = System.nanoTime();
  System.out.println(minCoins(coins, amount));
  System.out.println("Time1: "+(System.nanoTime() - time));
  
  long time2 = System.nanoTime();
  System.out.println(minCoinsWithBuf(coins, amount, buf2));
  System.out.println("Time2: "+(System.nanoTime() - time2));
  
  
  long time3 = System.nanoTime();
  System.out.println(minCoinsDP(coins, amount, buf1));
  System.out.println("Time3: "+(System.nanoTime() - time3)); 
  
       }