问题描述 链接到标题

871.最低加油次数

解题思路 链接到标题

动态规划 链接到标题

对于这种有限次数，能看出来有递推关系的，可以考虑动态规划。

这里状态记为dp[i][j]，表示经过前i个加油站，加j次油之后，能够到达的最远距离，这里显然有i >= j。

那么考虑dp[i][j]的递推关系，可以分在第i个加油站加油和不加油两种情况来讨论：

  • 在第i个加油站不加油：dp[i][j] = dp[i - 1][j]
  • 在第i个加油站加油（要求第i个加油站可以在之前只加了j - 1次油的情况下到达），即dp[i - 1][j - 1] >= stations[i - 1][0]，此时dp[i][j] = dp[i - 1][j - 1] + stations[i - 1][1]

dp[i][j]取两者中的最大值

贪心 链接到标题

首先，很容易想到，最佳策略每次加油，都是在油最多的加油站去加油，这里实际上可以认为能直接从经过的加油站中取油，即每次发现到达不了下一个加油站或者终点了，就从已经经过但是没加过油的加油站里加油，直到可以到达下一个加油站或者终点，可以利用优先队列来模拟这个过程，每次需要更新剩余的燃油cur_fuel。

代码 链接到标题

动态规划 链接到标题 

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++) {
                // 如果stations[i - 1](第i个加油站可以在dp[i - 1][j - 1]的情况下到达)
                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;
    }
};

贪心 链接到标题 

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); // 油最多的加油站在堆顶
        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]) {
                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;
    }
};