def minRefuelStops_DP(
    target_distance: int, start_fuel: int, stations: list[list[int]]
) -> int:
    """1-D Dynamic Programming

    DP_table[num_stops]
        the furthest distance (== max gas) that we can get
        with num_stops times of refueling.

    So for every station, stations[i],
        if the current distance DP_table[num_stops] >= stations[i][0], we can refuel:
            DP_table[num_stops + 1] = max(
                DP_table[num_stops + 1],
                DP_table[num_stops] + stations[i][1]
                )

    In the end, we'll return
        the first num_stops with DP_table[num_stops] >= target,
        otherwise -1.

    Complexity:
        n = len(stations)
            Time: O(n^2)
            Space: O(n) for the DP table

    Args:
        target_distance:
        start_fuel:
        stations: list of [distance, gallon] pairs, in sorted order of distance

    Returns: LEAST # of stops to destination OR -1 if not possible

    Examples:
        >>> stations = [[10,60],[20,30],[30,30],[60,40]]
        >>> minRefuelStops_DP(target_distance=100, start_fuel=10, stations=stations)
        2
        >>> minRefuelStops_DP(target_distance=100, start_fuel=1, stations=stations)
        -1
        >>> minRefuelStops_DP(target_distance=1, start_fuel=1, stations=[])
        0
        >>> stations = [[10,10],[20,10],[30,30],[60,40]]
        >>> minRefuelStops_DP(target_distance=100, start_fuel=10, stations=stations)
        4

    """
    ## Initialize

    # vars
    pass

    # DS's/res
    # DP_table[num_stops]<=> furthest distance (== max gas) possible if refueling num_stops times.
    DP_table = [start_fuel] + [0] * len(stations)  # |DP_table| == len(stations) + 1

    ## POPULATE the table
    for station_i in range(len(stations)):

        # Check all stops ≤ current station_idx
        # Updates values from the worst case (all stations) to the best case (0 stations)
        for num_stops in range(station_i + 1)[::-1]:  # Backwards iteration
            station_distance, station_fuel = stations[station_i]

            curr_fuel = DP_table[num_stops]
            if curr_fuel >= station_distance:  # station is reachable
                ## VISIT station
                # update if a better option was found
                DP_table[num_stops + 1] = max(
                    DP_table[num_stops + 1], curr_fuel + station_fuel
                )

    ## FIND OPTIMAL value
    # Return the 1st min number of stops
    # where distance traveled ≥ target distance
    for num_stops, travel_distance in enumerate(DP_table):
        if travel_distance >= target_distance:
            return num_stops

    return -1