New answers tagged dynamic-programming
2
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 ...
Top 50 recent answers are included
