本次刷题日记的第 78 篇，力扣题为：871. 最低加油次数，困难
一、题目描述：
最近油价高居不下，甚至还有上涨的趋势，我们今天就来计算一下达到目的地，如何加油次数最少，871. 最低加油次数
二、这道题考察了什么思想？你的思路是什么？
还是来看一下题目给了我们那些重要的信息:
- 汽车从出发地到目的地距离为 target ，汽车启动的时候，有油 startFuel 升，对应就可以跑 startFuel 英里
- 途中有很多个加油站，车子到每一个加油站，如果决定加油的话，则会将加油站所有的油全部加到车子油箱中，土豪吧
- 那么题目需要我们找到，从出发地到目的地最少的加油次数
分析
其实就这么来看，简单的想法是不是会想到，我的车开出去，前几个加油站我都加油，直到全部加的油能够跑 target 英里就可以了，这样岂不是很简单？
实际上稍微想想就知道，这样确实很省事，但是并不一定是最低的加油次数
那么一点，我们是可以明确的，那就是加油站相对出发地的距离，一定是递增的，而且对于每一个加油站，我们也能够间接知道我们当前是否可以跑到目的地，或者是间接知道，当前我是否需要加油，如何间接知道呢？我们可以倒推
例如咱们出发地的时候，dp [0] 就表示能够跑的英里数，自然 dp[0] = startFuel
那么我们令加油站的位置为 i，加油的次数为 j，那么我们就有
dp[j]=dp[j−1]+stations[i][1]dp[j] = dp[j-1] + stations[i][1] dp[j]=dp[j−1]+stations[i][1]
满足上述公式的前提是 dp[j-1] 是 >= stations[i][0] 的 ， 很明显，只有汽车中的油能够坚持到 stations[i][0] 的位置，才有机会加油，如果都没有机会坚持到加油站，那么何谈加油呢
那么我们推到 dp 的时候，我们如何来做到 dp 里面存储的数据，是能够满足加油次数最少的呢？
简单理解就是，我们在经过当前加油站的时候，要看当前不加油的话，是否能够满足到达下一个，或者下下个加油站，如果可以，那么肯定是到了哪个加油站再去加
可也会存在这么一个情况，当前不加油，到了之后的加油站才加，可能会出现加了油也没有办法到达目的地
因此我们可以这样来推导 dp，汽车走过每一个加油站的时候，来计算 dp 当到当前位置的最大值
target = 100, startFuel = 10,
| [10,60], | [20,30], | [30,30], | [60,40] |
例如上面这个例子
咱们推导出来，肯定是只在 第一个加油站和 第四个加油站加油，我们即可开到目的地，即加 两次油
开到第一个加油站的 dp 情况
dp[0]=10
dp[1]=70
开到第二个加油站的 dp 情况
dp[2]=100
开到第三个加油站的 dp 情况
dp[3]=130
dp[2]=100
开到第四个加油站的 dp 情况
dp[4]=170
dp[3]=140
dp[2]=110
剩下的就来看看代码的实现情况吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码如下：
func minRefuelStops(target int, startFuel int, stations [][]int) int { dp := make([]int,len(stations)+1) dp[0] = startFuel for i,sta := range stations { // 这一层主要是确认 dp 实际应该存放的值，因为并不是每一个加油站我们都是要默认加油的，我们要尽可能的少加油 for j:=i; j>=0 ;j--{ if dp[j] >= sta[0] { dp[j + 1] = max(dp[j+1], dp[j] + sta[1]) } } } for i,v := range dp { if v >= target { return i } } return -1 } func max(a,b int) int { if a>b { return a } return b }
四、总结：
看咱们的实现方式，对于时间复杂度还是比较容易看出来的，时间复杂度是 O(n^2) ，嵌套了 2 层循环，第一层和第二层循环的次数都是加油站的个数 n
空间复杂度是 O(n) ， 我们开辟了 O(n) 的空间 dp 来帮助我们推到数据
原题地址：871. 最低加油次数
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
