Youre driving from San Francisco, CA to SB, NY. There are gas stations along the way at distance x1, x2, . . . , xn from San Francisco. Because of different wait times and pump speeds, filling up at gas station xi takes ci minutes (the gas costs the same everywhere, so we ignore its cost). 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. Give a dynamic programming algorithm that finds where you should stop to spend the minimum amount of time at gas stations during your trip.

Hint: you know youll have to stop at a gas station within 100 miles of SB, for example.

C6 ?7 C2 C3C4C.5 SB SF. X3 X4X5 *6 X1X2