Gas Station-like Algorithm with minimum cost? Greedy or DP?

Question

I have an array of n service stations D[] on a highway such that D[i] is the distance of the station i from the start of the highway.

I also have an array of costs C[] such that C[i] is the cost of getting my vehicle serviced at station i.

I have to get my car serviced at the first station, and my car can travel at most 100 miles between stations.

What is the most efficient algorithm to get from the start of the highway to the end with the least cost (I need to know which stations to stop at)? I was able to find a greedy solution for minimizing the number of stops, but for the least cost, I am thinking DP, with the optimal subproblem:

bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

and have a separate array last[j] which contains the last station at which to stop, which would be the best i from above subproblem.

Would this be the right approach, or is there a better Greedy / DP solution?

Answer 1

The recurrence is better written as

bestcost_serviced_at[j] =
  min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)

because the recurrence gives the optimal cost assuming that the vehicle actually stops at station j for service.

Then the solution to the problem is

min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)

I don't think a greedy algorithm would work.