871. 最低加油次数

Problem: 871. 最低加油次数

1.动态规划

思路

起初看到题目的规模不大，便以为可以使用$O(n^2)$的算法来做，这是想到用动态规划的一个契机。

再就是题目是符合动态规划的条件的：

1. 题目符合无后效性，后面的加油站的选择对前面没有影响。
2. 题目存在最优子结构，即我们可以通过构造dp[i][j]，其中i表示到达第i站，加了j次油时所剩的油，通过不断扩大i的规模即可求解。

起初，设定dp[0][0]为startFuel - stations[0][0]，表示到达第0站而且未加油，如果这个值大于0，则可以加上stations[0][1]。

之后我们遍历i，并从大到小遍历所有小于等于i的j，判断dp[i-1][j]能否到达第i站，如果可以，而且这样剩的油更多的话，则更新dp[i][j + 1]。这里注意到，由于dp[i]之和前dp[i - 1]有关，我们可以省略这一维度。而我们从大到小遍历j，可以防止在更新过程中用dp[i][j + 1]的值覆盖之前dp[i - 1][j + 1]的值。

最后在遍历结束后，我们找出最小的所剩油量足够行驶完剩余距离的次数即可。

复杂度

• 时间复杂度: $O(n^2)$：双层for循环，n为数组长度。
• 空间复杂度: $O(n)$：动态规划所用空间。

Code

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        if (n == 0){
            return target <= startFuel ? 0 : -1;
        } 
        //到第i站，加油j次所剩的油。
        int dp[] = new int[n + 1];
        dp[0] = startFuel - stations[0][0];
        if (dp[0] >= 0) dp[1] = dp[0] + stations[0][1];
        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] < 0) continue;
                dp[j] = dp[j] + stations[i - 1][0] - stations[i][0];
                if (dp[j] >= 0) dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
            }
        }
        int remain = target - stations[n - 1][0];
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= remain) return i;
        }
        return -1;
    }
}

2.贪心

思路

本题实际上有更好的做法。要知道，能够使用动态规划解决的题目就有可能能用贪心解决。

想象这样一个情景，车在行驶的过程中，如果身上的油足够它走过接下来若干个加油站，那么它如果要加油次数最少，肯定要在这些加油站中选一个能加最多油的站先加上。

这样做的情况下加油次数最少是保证了，但是能否确保不会因为少加油而无法到达终点？

这是可能存在的，但是实际上由于要到达终点我们会经过所有的加油站，如果后面发现油不够了，只要还记住没有加油的站里哪个油最多，一一再加上也是可以的（反悔）。

上面我们发现，我们需要维护的是已经到达的站按油量最多排序的优先队列，再加上贪心即可解决问题。

复杂度

• 时间复杂度: $O(n)$：n为数组长度。
• 空间复杂度: $O(n)$：最大堆所用空间。

Code

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        if (n == 0){
            return target <= startFuel ? 0 : -1;
        }
        Queue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int nowFuel = startFuel;
        int nowPos = 0;
        int ret = 0;
        int cnt = 0;
        while (nowFuel < target - nowPos) {
            while (cnt < n && stations[cnt][0] <= nowFuel + nowPos) {
                q.add(stations[cnt++]);
            }
            if (q.isEmpty()) return -1;
            int[] add = q.poll();
            nowFuel += add[1] + nowPos - add[0];
            nowPos = add[0];
            ret++;
        }
        return ret;
    }
}