CODEWITHSUNDEEP
algorithmdynamic-programming
leller
leller

Reputation: 163

Dynamic programming algorithm for truck on road and fuel stops problem

A truck burns 1 unit of fuel while travelling 1 unit of distance. The truck has to reach town, which is located L units of distance along the road, and at the starting point the truck has P units of fuel in the tank (both values are given as (L,P) pair). The fuel tank is infinite, so the truck can always store more fuel. A number of possible fuel stops along the road is given as pairs of integers (a,b) where a is distance between the town and the fuel stop, and b is the number of fuel units that this fuel stop can provide.

The goal is to make as few stops as possible on the way to town. The algorithm must return the smallest number of stops required to make the trip.

I figured out how to solve this problem with a greedy algorithm, using a priority queue, but I'm struggling to find a dynamic approach to the problem. I know thet there is one, but I cannot figure it out. I'll appreciate any hints.

Upvotes: 1

Views: 1888

Answers (1)

v78
v78

Reputation: 2933

Idea copied from https://leetcode.com/problems/minimum-number-of-refueling-stops/solution/,

Let's determine dp[i], the farthest location we can get to using i refueling stops. This is motivated by the fact that we want the smallest i for which dp[i] >= target.

Algorithm

Let's update dp as we consider each station in order. With no stations, clearly we can get a maximum distance of startFuel with 0 refueling stops.

Now let's look at the update step. When adding a station station[i] = (location, capacity), any time we could reach this station with t refueling stops, we can now reach capacity further with t+1 refueling stops.

For example, if we could reach a distance of 15 with 1 refueling stop, and now we added a station at location 10 with 30 liters of fuel, then we could potentially reach a distance of 45 with 2 refueling stops.

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int N = stations.length;
    long[] dp = new long[N + 1];
    dp[0] = startFuel;
    for (int i = 0; i < N; ++i)
        for (int t = i; t >= 0; --t)
            if (dp[t] >= stations[i][0])
                dp[t+1] = Math.max(dp[t+1], dp[t] + (long) stations[i][1]);

    for (int i = 0; i <= N; ++i)
        if (dp[i] >= target) return i;
    return -1;
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of stations.

Space Complexity: O(N), the space used by dp.

Upvotes: 1

Related Questions