Description Link to heading

871.minimum-number-of-refueling-stops

Solution Link to heading

Dynamic programming Link to heading

In this problem, the number is finite, and there is a recurrence relation, so we can use dynamic programming to solve this problem.

Let dp[i][j] means the furthest distance we can reach after passing throught i stations and adding fuel for j times. Obviously, i >= j.

So we can discuss dp[i][j] in two cases:

  • We don’t add fuel at the ith station: dp[i][j] = dp[i - 1][j]
  • We add fuel in the ith station(We have to arrive at the ith station in the case we have just added fuel for j - 1 times before, that is: dp[i - 1][j - 1] >= stations[i - 1][0]): dp[i][j] = dp[i - 1][j - 1] + stations[i - 1][1].

dp[i][j] is the maximum value of the two values.

Greedy algorithm Link to heading

It is easy to see that the optimal strategy is to add fuel in the station with the most fuel. Actually, we can get fuel from the station that we passed through. For each time we can’t get to the next station or destination, we get fuel from the station with the most fuel that we passed through but didn’t get fuel from, until we get to the next station or destination or there is no station we can get fuel from.

Code Link to heading

Dynamic programming Link to heading 

class Solution {
  public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) {
        int n = stations.size();
        if (n == 0) {
            if (startFuel >= target)
                return 0;
            return -1;
        }
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
        dp[0][0] = startFuel;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = stations[i - 1][0] <= startFuel ? startFuel : 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // We have to arrive at the `i`th station in the case we have just added fuel for `j - 1` times before,
                if (dp[i - 1][j - 1] >= stations[i - 1][0])
                    dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        int res = 600;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[i][j] >= target)
                    res = std::min(res, j);
            }
        }
        return res >= 600 ? -1 : res;
    }
};

Greedy algorithm Link to heading 

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size();
        if (n == 0) {
            if (startFuel >= target)
                return 0;
            return -1;
        }
        if (startFuel < stations[0][0])
            return -1;
        int res = 0;
        auto cmp = [&](vector<int> &v1, vector<int> &v2){
            return v1[1] <= v2[1];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp); // heap top is the station with the most fuel
        pq.push(stations[0]);
        int cur_fuel = startFuel - stations[0][0];
        for (int i = 1; i < n; i++) {
            while (!pq.empty() && cur_fuel < stations[i][0] - stations[i - 1][0]) { // notice the **while**, and judge if pq is empty first!
                cur_fuel += pq.top()[1];
                pq.pop();
                res++;
            }
            if (cur_fuel < stations[i][0] - stations[i - 1][0]) {
                return -1;
            }
            pq.push(stations[i]);
            cur_fuel = cur_fuel - (stations[i][0] - stations[i - 1][0]);
        }
        while (!pq.empty() && cur_fuel < target - stations[n - 1][0]) {
            cur_fuel += pq.top()[1];
            res++;
            pq.pop();
        }
        if (cur_fuel < target - stations[n - 1][0])
            return -1;
        return res;
    }
};