1
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

Your dynamic programming approach looks fairly similar to this in many respects (just with a bit more casework, maybe).

$\endgroup$
2
  • $\begingroup$ Thank you a lot for your help, this way it seems way simpler. I find it very tricky to understand when to use dynamic programming instead of greedy, but I guess I should try greedy before always. Thanks again! $\endgroup$ Commented Jan 3 at 23:12
  • $\begingroup$ @FarsoFracico you can read CLRS' greedy chapter to see how you can always try to turn a dynamic programming solution into a greedy solution, by proving that only one subproblem would remain by then and other things, since there's always a dynamic programming underpinning of a greedy solution namely optimal substructure $\endgroup$ Commented Jan 8 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.