# Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific excersise. This is the text:

Matt is planning a road trip from City A to City B, and he wants to minimize the number of breaks during the journey. He has a limit of n kilometers he can drive before needing a break. His map includes the distances between rest stops along the route.

The problem is simalar to the one appearing in this question, but the answers do not really go in depth about the actual algorithm

I am trying to build the algorithm with dynamic programming. The main idea is that for each possible stop, I check what is more convenient between stopping and not stopping. This is what I have come up with:

$$OPT(km, i) = \left\{\begin{matrix} 1+OPT(km, i+1) & d_i > km \\ min(1+OPT(km, i+1), OPT(n-d_i, i+1)) & d_i\leq km\\ 0 & i=n \end{matrix}\right.$$

Where $$i$$ is the number of the station, $$n$$ is the total number of stations, $$km$$ is the maximum drivable distance without stopping and $$d_i$$ is the distance between the $$i$$'th station and the previous one.

I have thought about making it more efficient by using memoization, but I don't see how this could be done since the number of km left might vary between every call to $$OPT$$. I have no clue about how to prove that this algorithm actually gives the best possible solution, nor do I know what its time complexity is. I guess each call to $$OPT$$ is constant time, but the number of subproblems seems big.

Any help will be gratly appreciated!

As it turns out, you don't need any dynamic programming to solve this problem, and a greedy solution works great. The greedy solution is: go as far as possible without taking a break from City $$A$$ (i.e. go to the furthest rest stop which is less than $$n$$ kilometers away). Repeat this process until you reach City $$B$$. This runs in time $$O(n)$$ by using, say, two pointers.
Why can we do this? Well, let $$f(i)$$ be the minimum number of breaks you need to reach rest stop $$i$$ (let's define City $$A$$ to be rest stop $$0$$ and City $$B$$ to be rest stop $$m$$). Then, $$f(0) \le f(1)\le f(2) \le \ldots \le f(m)$$.
Now, let's suppose we have computed $$f(0), f(1), \ldots, f(i - 1)$$. How can we compute $$f(i)$$? We may write $$f(i) = 1 + \min_{j < i, d(i, j) \le n} f(j)$$, where $$d(i, j) = d(i, 0) - d(j, 0)$$ is the distance between rest stops $$i$$ and $$j$$. By the increasing assumption on $$f(j)$$, it follows that $$f(i)$$ only depends on the single furthest before it coordinate $$j$$, which is identical to the greedy approach in the first paragraph.