经典算法专区：最低加油次数（二）

思路和算法由于数组 stations 按照加油站的位置非递减排序因此从左到右遍历数组 stations 的过程中当遍历到一个加油站时位置小于该加油站的所有加油站都已经被遍历过。用 n 表示数组 stations 的长度即加油站的个数。最多可以加油 n 次为了得到可以到达目的地的最少加油次数需要计算每个加油次数对应的最大行驶英里数然后得到最大行驶英里数大于等于 target 的最少加油次数。用 dp[i] 表示加油 i 次的最大行驶英里数。由于初始时汽油量是 startFuel 升可以行驶 startFuel 英里因此 dp[0]startFuel 。当遍历到加油站 stations[i] 时假设在到达该加油站之前已经加油 j 次其中 0 ≤ j ≤ i 则只有当 dp[j] ≥ stations[i][0] 时才能在加油 j 次的情况下到达加油站 stations[i] 的位置在加油站 stations[i] 加油之后共加油 j1 次可以行驶的英里数是 dp[j] stations[i][1] 。遍历满足 0 ≤ j ≤ i 且 dp[j] ≥ stations[i][0] 的每个下标 j 计算 dp[j1] 的最大值。当遍历到加油站 stations[i] 时对于每个符合要求的下标 j 计算 dp[j1] 时都是将加油站 stations[i] 作为最后一次加油的加油站。为了确保每个 dp[j1] 的计算中加油站 stations[i] 只会被计算一次应该按照从大到小的顺序遍历下标 j 。以示例 3 为例。对于加油站 stations [2] 计算之后dp[2] 100 。对于加油站 stations[3] 计算的过程中会将 dp[2] 的值更新为 110 。如果在计算 dp[3] 之前计算 dp[2] 则 dp[3] 的值将被错误地计算为 dp[2] stations[3][1] 150 。只有当从大到小遍历下标 j 时才能得到 dp[3] 140 的正确结果。当所有的加油站遍历结束之后遍历 dp 寻找使得 dp[i] ≥ target 的最小下标 i 并返回。如果不存在这样的下标则无法到达目的地返回 −1 。代码Python3class Solution: def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) - int: dp [startFuel] [0] * len(stations) for i, (pos, fuel) in enumerate(stations): for j in range(i, -1, -1): if dp[j] pos: dp[j 1] max(dp[j 1], dp[j] fuel) return next((i for i, v in enumerate(dp) if v target), -1)Javaclass Solution { 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 j i; j 0; j--) { if (dp[j] stations[i][0]) { dp[j 1] Math.max(dp[j 1], dp[j] stations[i][1]); } } } for (int i 0; i n; i) { if (dp[i] target) { return i; } } return -1; } }复杂度分析时间复杂度O(n*2) 其中 n 是数组 stations 的长度。动态规划的状态数是 O(n) 每个状态需要 O(n) 的时间计算因此时间复杂度是 O(n*2) 。空间复杂度O(n) 其中 n 是数组 stations 的长度。需要创建长度为 n1 的数组 dp 。