Problem Statement |
| | Character j in element i (both 0-based) 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 1e-9 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 N-1 inclusive, where N is the number of elements in prices. |
| - | endLocation will be between 0 and N-1 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 | |
|