题：https://leetcode.com/problems/minimum-number-of-refueling-stops/

题目大意

起点有油 startFuel 的车，想行驶到 终点 target位置。途中有多个加油站 station 可以加油，其中station[0] 表示与起点的距离，station[1]表示可以加的油，且 车在行驶过程中必须保持 油 >=0 。
求车能到达target的最少加油数，若不能达到 返回 -1。

思路

整个行驶过程十分像 0 -1 背包选择问题，对于每个加油站选择是否加油。

状态：
dp[i][j] : 经过 i 个加油站，加了 j 次油后，车能行驶的最远距离。

初始化状态：
dp[i][0] = startFuel ，若全程 未加油，那么车能行驶的里程便是 最初油startFuel 的 距离。

状态转移：
dp[i][j] = max(dp[i-][j], dp[i-1][j-1] + stations[i-1][1] if dp[i-1][j-1] >= stations[i-1][0] else 0)

这里的意思是：若在 i 加油站不加油，那么 dp[i][j] = dp[i-][j]，若选择加油 且 dp[i-1][j-1] >= stations[i-1][0] ，那么 dp[i][j] = max(dp[i-][j], dp[i-1][j-1] + stations[i-1][1] if dp[i-1][j-1] )

最后我们只用看 dp[stations.length][j]>= target 中的 最小 j 。

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {int N = stations.length;int[][] dp = new int[N+1][N+1];for(int i =0 ;i <= N ;i++)dp[i][0] = startFuel;for(int i = 1 ; i <= N ;i++)for(int j = 1 ; j <=N; j++){dp[i][j] = dp[i-1][j];if(dp[i-1][j-1] >= stations[i-1][0])dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + stations[i-1][1]);} for(int j = 0 ; j <= N ;j++)if(dp[N][j] >= target)return j;return -1;} }

0-1 背包 的典型压缩

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {PriorityQueue<Integer> pq = new PriorityQueue(new Comparator<Integer>(){public int compare(Integer o1,Integer o2){return o2 - o1;}});int dis = startFuel;int cnt = 0;int index = 0;while(true){if(dis >= target)return cnt;while(index < stations.length && stations[index][0] <= dis){pq.add(stations[index++][1]);}if(pq.isEmpty())break;dis += pq.peek();pq.poll();cnt++;}return -1;} }

方法二 贪心

车行驶，若车到达target，那么返回当前的加油次数。
若没有 用 大顶堆 记录 在油耗尽时 经过的 加油站，并将该加油站的加油数加入大顶堆中。
取 最大的 加油量 作为 车 能 增加的里程数数，继续上部操作。
当 大顶堆为空时，返回 -1
这里是用的贪心，不断去 反悔，假设 我们 取了 经过的 最好的加油站。

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {PriorityQueue<Integer> pq = new PriorityQueue(new Comparator<Integer>(){public int compare(Integer o1,Integer o2){return o2 - o1;}});int dis = startFuel;int cnt = 0;int index = 0;while(true){if(dis >= target)return cnt;while(index < stations.length && stations[index][0] <= dis){pq.add(stations[index++][1]);}if(pq.isEmpty())break;dis += pq.peek();pq.poll();cnt++;}return -1;} }

总结

以上是生活随笔为你收集整理的[LeetCode] 871. Minimum Number of Refueling Stops的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。