Solution: Car Fueling

Solution 1: Recursive algorithm

We are going to be greedy; when approaching a gas station, we only stop there if we cannot reach the next one without running out of gas. Pictorially, this looks as follows:

To prove that this strategy leads to an optimum solution, assume that $stop_{k}$ is the farthest reachable station. On one hand, it is reachable on a full tank ($stop_{k} ≤ m$). On the other hand, the next station is not reachable ($stop_{k+1} > d$). We claim that there must be an optimum solution where the first refuel is at $stop_{k}$. To prove this, take an optimum solution and let $stop_{i}$ ...