871. Minimum Number of Refueling Stops

https://leetcode.com/problems/minimum-number-of-refueling-stops/

Python

Bottom Up DP

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        dp = [0] * (len(stations)+1)
        dp[0] = startFuel

        dp = [startFuel] + [0] * len(stations)
        for i, (location, capacity) in enumerate(stations):
            for t in range(i, -1, -1):
                if dp[t] >= location:
                    dp[t+1] = max(dp[t+1], dp[t] + capacity)

        for i, dest in enumerate(dp):
            if dest >= target:
                return i

        return -1