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.
Best 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.