Here is the question:
You are doing the Tour de France and you are given a map with all the n places where you can refill your water bottles. Your bottles fit 2 liters of water with which are enough for m kilometres. Your goal is to stop as few times as possible to refill your bottles, since you care about a good time for the Tour de France. Design an efficient algorithm using dynamic programming, prove its correctness and analysis its run time. Give the one-dimensional array A. And the time complexity of filling your array.
I just confuse about this question. And what is the motivation to use dynamic programming.I think it looks like bin packing problem without change the order of choice. Why not use greedy next fit approach(e.g refill at kth station if we can't reach k+1th station without refill)could someone give some hint? Thanks