最低加油次数

发表于 分类于

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-refueling-stops

题目

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

思路

一开始想的是贪心+回溯。

每次到一个加油站，就不加油，尝试能不能走到下一个加油站，如果不行则回溯回来加油。之后个别数据WA，发现如果这次不加油可以到下一加油站，可能会造成之后的加油次数变多。例如一开始油很多，第一个加油站油也很多，只要加一次就可以走到终点，但是不加直接前往下一加油站，会造成后面要加多次油才能到终点。

遂去除了贪心，直接回溯/分治/递归。

每次都把当前位置加与不加计算一遍，果不其然超时了。但是这种方法让我想起了背包问题，而背包问题是可以使用动态规划求解的。

在尝试找动态规划的转移方程当前状态对下一状态的影响的时候发现与背包问题的不同。首先背包是有容量限制的，物品重量和价格是非等价的。而加油容量是有上限的，限制的是加油次数，而加油的多少是和距离等价的。于是想到只要每次加油量是最多的，当前状态最优的，那总加油次数肯定是最少的，行驶距离最远。

于是又走回贪心。

计算不加油的情况下能走多远，如果到不了终点，那就在可以到达的加油站里选一个油量最多的加。然后继续判断能否到达终点，选最多油量的。

总结

在写代码的时候判断加油量最多的算法用的是O（n）的顺序查找，靠一个map来记录是否已经取过值，总体时间复杂度是O（n2），而如果用优先队列，查找最大值是O（1），插入删除是O（logn），总体时间复杂度是O（nlogn），有待优化。

其次就是动态规划，还是不太熟悉，希望之后能加强练习吧。