Dynamic Programming
The optimal refueling would look like a subsequence of (start, stations, target). For each station, we can find how far we can go with different number of refuelings. Then the minimum number of refuelings that gets us to the target is the answer.
Time: 
class Solution:
def minRefuelStops(
self, target: int, startFuel: int, stations: List[List[int]]
) -> int:
fuel_reach = [startFuel] + [0] * len(stations)
for i, (pos, fuel) in enumerate(stations):
for j in range(i, -1, -1):
if fuel_reach[j] < pos:
break
fuel_reach[j + 1] = max(fuel_reach[j + 1], fuel_reach[j] + fuel)
return next(
(count for count, reach in enumerate(fuel_reach) if reach >= target), -1
)
Greedy
We refuel only if we cannot reach the next station. When we need to refuel, we take the maximum fuel from the past.
Time: 
from heapq import heappush as push, heappop as pop
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
max_heap = []
stop_count = 0
curr_pos = 0
curr_fuel = startFuel
for i, (pos, fuel) in enumerate(stations):
if curr_pos + curr_fuel >= target:
return stop_count
while curr_pos + curr_fuel < pos:
if not max_heap:
return -1
curr_fuel += -pop(max_heap)
stop_count += 1
curr_fuel -= (pos - curr_pos)
curr_pos = pos
push(max_heap, -fuel)
while curr_pos + curr_fuel < target:
if not max_heap:
return -1
curr_fuel += -pop(max_heap)
stop_count += 1
return stop_count
unreasonably effective 
Leave a comment