871. Minimum Number of Refueling Stops

题目：

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can not reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Constraints:

• 1 <= target, startFuel <= 109
• 0 <= stations.length <= 500
• 0 <= positioni <= positioni+1 < target
• 1 <= fueli < 109

思路1：

第一反应是用递归来做，f[i][j]表示经过第 i 个加油站后，加油 j 次能够到达的最大距离，最后只需要找到最小的 j 并且f[i][j]大于等于target即可。状态转移方程中f[i][j]可以从三个地方来：1)f[i][j - 1]，代表经过了当前车站，但是不在当前车站加油；2)f[i - 1][j]，表示到达了第i - 1即前一个车站，并且加了j次油，即上个车站没加油；3)f[i - 1][j - 1] + stations[i - 1][1]，即经过了第i - 1个车站，并且在上个车站加了油，当然这里有条件就是f[i - 1][j - 1]的最大距离必须要比stations[i - 1][0]大，不然无法到达上个车站。初始化我们用 n = stations.size() + 1，即f[i][j]当 j 等于0 时表示f[i][0]都是没加过油的，那么它们的值应该为startFuel，至于f[0][j]，不需要初始化，因为j一定小于等i，即加油次数不能比路过的车站多。

代码1:

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size() + 1;
        vector<vector<long>> f(n, vector<long>(n));
        for (int i = 0; i < n; i++) {
            f[i][0] = startFuel;
        }      
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (f[i - 1][j - 1] >= stations[i - 1][0]) {
                    f[i][j] = f[i - 1][j - 1] + stations[i - 1][1];
                }
                f[i][j] = max({f[i - 1][j], f[i][j - 1], f[i][j]});
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                if (f[i][j] >= target)
                    return j;
            }
        }
        return -1;
    }
};

思路2：

从本质上来看，题目要求我们需要在最少的加油次数中加最多的油，即每次加油都加能够加的最多的油。但是我们每次路过车站，其实只有当前车站可以选择，那么怎么构成选项呢？答案是每次路过车站先不加油，把能够加的油记录进一个优先队列，等到需要加油的时候我们再取出来为自己加油。这里优先队列是为了管理最大值，使我们能够随时取出来的都是最多的油。首先我们能够到达的最大距离dist就是startFuel，之后判断dist和target，一旦dist大于等于target即可结束。循环中，每次我们路过车站，如果当前dist能够到达车站，那我们就先不加油，而是把油加入优先队列；如果不能到达车站，那么就加油，如果优先队列已经无油可加，证明我们不能到达target，直接返回-1；如果优先队列有油，那么就拿出最大的油，加给dist，同时更新加油次数即可。

代码2：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> q;
        int dist = startFuel, count = 0;
        int i = 0;
        while (dist < target) {
            if (i < stations.size() && dist >= stations[i][0]) {  //能到车站说明油暂时是够的
                q.push(stations[i][1]);  //先不加油，存起来
                i++;
            } else {
                if (q.size()) {  //有油可加
                    dist += q.top();    //加油
                    q.pop();
                    count++;  //更新次数
                } else {  //无油可加，无法到达target
                    return -1;
                }
            }
        }
        return count;
    }
};