Problem Statement 
 Character j in element i (both 0based) of prices gives the cost of a flight from location i to location j. Fortunately, the airline is having a special. Each time you arrive at a location k, all future flights to location k (from anywhere) become half price (no rounding). These savings build on each other. For example, if you arrive at location 2 twice, the next flight to location 2 is one quarter of the original price. Given startLocation and endLocation, the locations where you must start and end respectively, and num, the exact number of flights you must take, return the smallest possible total cost. You cannot take a flight from a location back to itself. 

Definition 
 Class:  CheapestFlights  Method:  getLowest  Parameters:  String[], int, int, int  Returns:  double  Method signature:  double getLowest(String[] prices, int startLocation, int endLocation, int num)  (be sure your method is public) 




Notes 
  You may revisit a location numerous times. 
  The returned value must be accurate to 1e9 relative or absolute. 

Constraints 
  prices will contain between 3 and 8 elements inclusive. 
  Each element of prices will contain N characters, where N is the number of elements in prices. 
  Each character in prices will be a digit ('0''9'). 
  startLocation will be between 0 and N1 inclusive, where N is the number of elements in prices. 
  endLocation will be between 0 and N1 inclusive, where N is the number of elements in prices. 
  num will be between 2 and 8 inclusive. 

Examples 
0)  
 {"019",
"909",
"990"
}  0  1  2 
 Returns: 18.0  You must take 2 flights, so you go from location 0 to location 2, and then location 2 to location 1. 


1)  
 {"099",
"909",
"990"
}  0  1  3 
 Returns: 22.5  Your path is:Location 0 > Location 1 > Location 0 > Location 1
The respective costs are 9, 9, and 4.5. 


2)  
 {"099",
"909",
"990"
}  0  1  7 
 Returns: 32.625  

3)  
 {"111",
"111",
"111"
}  1  1  8 
 Returns: 3.75  
