仅最优-最少停靠点和哪些停靠点

Question

什么是最优的算法，为从P1到Pn的路线提供最少的加油站编号数组，其中Pi是加油站，

1 <= i <= n，(包括起点P1和目的地Pn)。

距离向量Dist 1...n-1，其中，n=可用加油站的总数，Dist i是从Pi到Pi+1的距离。

向量将分别是集合Dist P1 - P2，…，Pn-1 - Pn。

假设：

1.每个加油站都给你的车加满了油箱。

2.你的车可以行驶‘d’英里，只要它充满了‘p’升的油箱。

3油站之间的距离假定不大于‘d’(Dist i <= d)。(这就是说，如果汽车只是加了油，就不能在中途耗尽油站之间的燃料)

4.你从P1加满了汽油，开始了你的旅程。

Answer 1

贪婪的方法是最优的。总是去你能到达的最远的车站，而不需要加油。O(n)。

为什么？假设A、B和C是沿途的三个站点，按照到达的顺序，您可以从站点A访问B或C，而不需要加油。如果你在B处加油，那么当你到达C处时，停站的次数与在C处停留的次数一样多，但燃料更少。