# Dynamic programming problem finding the subproblem

There are gas stations along the way at distance $a_1, a_2, \ldots , a_n$ from place A to place B. Filling up at gas station $a_i$ takes $m_i$ minutes. Your car can hold enough gas to go 100 miles, and you start with a full tank of gas. If you decide to stop at a gas station, you have to fill your entire tank up.

How can I solve this problem via dynamic programming that finds where to stop and spend the minimum amount of time at gas stations during the trip?

For here, the fuel cost is ignored and all we care about is the minimum time.

• You are leaving out some important details. How much fuel is spent per distance travelled? How are the gas stations and A and B connected? A graph of some kind? Do you really want to just minimize the time spent refuelling or the total time spent refuelling and travelling? – mikkola Nov 9 '15 at 7:06
• Fuel cost are ignored and only the minimum time is considered here. – good2know Nov 9 '15 at 17:51
• @mikkola, to my understanding the author means that AB is a segment (he didn't tell us the length...) and the gas stations are along it. And also that trip time = constant + sum of time spent at the stations – Pavel Yudaev Nov 9 '15 at 19:45
• Have a look at the book "Algorithms" by Dasgupta. He has an excellent treatment of dynamic programming. – K. Miller Nov 11 '15 at 13:53

## 1 Answer

Firstly, if C is between A and B and belongs to an optimal solution, then CB is also optimal. Hence DP can be applied.

Are $a_i$'s real or integer numbers? Solution for integers is below. I believe it could be adapted for real $a_i$'s as well. Fortunately the fuel tank capacity is an integer.

The solution.

X-axis: current distance to B in miles. Integers from $0$ to $L=AB$ with gas stations (GS) marked. $0$ on the left.
Y-axis: current fuel in the tank (in miles), integers from $0$ to capacity = $100$, with $0$ on top. I tried a simulation with the tank capacity = $4$ and $AB$ distance = $11$ miles and a few GS's.

If $x=0$, cell score is $0$ as we're at B.

From a general cell in $k$-th row you can go diagonal up-left up to $k$ steps. You must either reach $B$ or a GS. Cell score = minimum of scores of reachable cells. If you can neither reach a GS or $B$, the destination is unreachable, score = $\infty$.

From a cell in $k$-th row when there's a GS on the X-axis, you can go either (a) up-left up to $k$ steps, or (b) go down to $100$-th row (same column). In the (b) case, the original cell score = score of that one you reach plus $m_i$.

From any cell in the $100$-th row you can only move up-left for up to $100$ diagonal steps.

That's it.