今天的小技巧：最少加油次数的方法

今天和闺蜜聊天，问我为啥很久没更新文章了，说她一直关注我。
其实最近有在学习，但是不知道写什么，感觉自己的知识面太宅了，深度也非常的欠缺。

写一个算法的题解吧

题目

[题目来源]：871. 最低加油次数（leetcode）
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

答案

var minRefuelStops = function(target, startFuel, stations) {
    const n = stations.length;
    // 记录每次加油后可到达的距离
    const dp = new Array(n + 1).fill(0);
    dp[0] = startFuel;
    for(let i = 0; i < n; i++) {
        const [curStation, curFuel] = stations[i];
        
        // 到j站点可以到达的距离
        let j = i;
        while(j >= 0 && dp[j] >= curStation) {
            dp[j + 1] = Math.max(dp[j + 1], dp[j] + curFuel);
            console.log(i, j, dp);
            j--;
            
        }
        
    }
    return dp.findIndex(item => item >= target);
};

分析

核心思路：最小的加油次数，到达最远的距离。 在到达本站点的时候，我们可以选择加油或者不加油，加油与不加油是有下一个站点是否能到达决定。
那我们就可以换种思考方式，假设到本站点都加油（记录加油和的距离），但后再看前面的j次加油，是否也能到达本站点，如果能则可以拿到本次的油量（这样说有点抽象，可以看下面的举例说明） 那首先我们可以声明一个变量dp保存第i次加油后能到达的距离，第0次加油的值就为startFuel。

举例说明：
target = 100, startFuel = 10, stations = [[10, 20], [20, 30], [30, 40], [60, 50]]

i	j	curStation	curFuel	dp	备注
-	-	-	-	[10, 0, 0, 0, 0]
0	0	10	20	[10, 30, 0, 0, 0]
1	1	20	30	[10, 30, 60, 0, 0]
1	0	20	30	[10, 30, 60, 0, 0]	不会进入while, dp[0] < 20
2	2	30	40	[10, 30, 60, 100, 0]
2	1	30	40	[10, 30, 70, 100, 0]
2	0	30	40	[10, 30, 70, 100, 0]	不会进入while, dp[0] < 30
3	3	60	50	[10, 30, 60, 100, 150]
3	2	60	50	[10, 30, 70, 110, 150]
3	1	60	50	[10, 30, 70, 110, 150]	不会进入while, dp[1] < 30

今天的内容就到这儿吧，想想后面的计划