Gas Station problem : Fixed path variation
The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).

The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this solution is in fact identical to the greedy one (to understand why this almost always works, you can read up on matroids and see how the standard proof is done in this case).

Informally, in this case :

Call GS your greedy strategy and let OPTS be an optimal strategy which agrees with GS for the longest time, starting from the beginning. Suppose GS and OPTS differ in strategy for the first time in city C: 


If OPTS fuels up more than GS at this point, then that means that GS fueled up just enough to reach the next cheapest city C'. It is clear that OPTS will arrive in C' with more fuel than GS (more than 0). But GS can then fill its tank up to as much as OPTS (for cheaper than OPTS could have at any point between C and C'). We can thus construct an optimal strategy OPTS' which does what GS does up to C' and then copies OPTS. But OPTS' is optimal and "agrees with GS" for longer than OPTS, which is impossible by definition of OPTS. So it is impossible that OPTS fuels up more than GS in C.
If OPTS fuels up less than GS in C, then let C' be the next city where OPTS is gonna fuel up. C' can not be cheaper than C, otherwise GS would have filled up just enough to get there and OPTS would have had to fuel up at some point between C and C'. So C' is as least as expensive as C, and filling up in C would not have been worse for OPTS. We can once again construct a new strategy OPTS' which contradicts the definition of OPTS. So it is impossible that OPTS fuels up less than GS in C.


Putting both together, we see that there can not be a "first disagreement point" between GS and OPTS. Thus, GS = OPTS, and GS is an optimal strategy.