插： 前些天发现了一个巨牛的人工智能学习网站，寻常易懂，风趣幽默，不由得分享一下给各人。点击跳转到网站。
坚韧不拔，越积极越荣幸，各人一起学习鸭~~~
2哥：3妹, 第3题要不要挑衅一下本身，做一道 hard的吧
3妹：哈？？hard对于我来说也太难了，寻常我标题都不敢看的。
2哥：嗯，有些herd题是挺难的。着实只要理清楚了思绪，有些hard并没有想象的那么难。
3妹：好吧，我实行一下。
标题：
汽车从出发点出发驶向目标地，该目标职位于出发位置东面 target 英里处。
沿途有加油站，每个 station 代表一个加油站，它位于出发位置东面 station[0] 英里处，而且有 station[1] 升汽油。
假设汽车油箱的容量是无穷的，此中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时，它大概停下来加油，将全部汽油从加油站转移到汽车中。
为了到达目标地，汽车所须要的最低加油次数是多少？假如无法到达目标地，则返回 -1 。
注意：假如汽车到达加油站时剩余燃料为 0，它仍然可以在那边加油。假如汽车到达目标地时剩余燃料为 0，仍然以为它已经到达目标地。
示例 1：
输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目标地。
示例 2：
输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：我们无法抵达目标地，乃至无法到达第一个加油站。
示例 3：
输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
我们出发时有 10 升燃料。
我们开车来到距出发点 10 英里处的加油站，斲丧 10 升燃料。将汽油从 0 升加到 60 升。
然后，我们从 10 英里处的加油站开到 60 英里处的加油站（斲丧 50 升燃料），
并将汽油从 10 升加到 50 升。然后我们开车抵达目标地。
我们沿途在1两个加油站停靠，以是返回 2 。
提示：
1 <= target, startFuel, stations[1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
思绪：
使用动态规划，
由于数组 按照加油站的位置非递减排序，因此从左到右遍历数组的过程中，当遍历到一个加油站时，位置小于该加油站的全部加油站都已经被遍历过。
用 n表现数组stations 的长度，即加油站的个数。最多可以加油 n次，为了得到可以到达目标地的最少加油次数，必要盘算每个加油次数对应的最大行驶英里数，然后得到最大行驶英里数大于即是 target 的最少加油次数。
用dp 表现加油 i 次的最大行驶英里数。由于初始时汽油量是startFuel 升，可以行驶 startFuel 英里，因此dp[0]=startFuel。
当遍历到加油站 stations 时，假设在到达该加油站之前已经加油 j次，此中0≤j≤i，则只有当 dp[j]≥stations[0] 时才华在加油 j 次的情况下到达加油站 stations 的位置，在加油站stations 加油之后，共加油j+1 次，可以行驶的英里数是 dp[j]+stations[1]。遍历满意0≤j≤i 且dp[j]≥stations[0] 的每个下标 j，盘算 dp[j+1] 的最大值。
当遍历到加油站 stations 时，对于每个符合要求的下标 j，盘算dp[j+1] 时都是将加油站 stations 作为末了一次加油的加油站。为了确保每个dp[j+1] 的盘算中，加油站stations 只会被盘算一次，应该按照从大到小的次序遍历下标 j。
当全部的加油站遍历竣事之后，遍历 dp，探求使得dp≥target 的最小下标 ii 并返回。假如不存在如许的下标，则无法到达目标地，返回 -1。
java代码：
class 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[0]) { dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[1]); } } } for (int i = 0; i <= n; i++) { if (dp >= target) { return i; } } return -1; }} |
