You and your friends are driving to Tijuana for springbreak. You are saving your money for the trip and so you want to minimize the cost of gas on the way. In order to minimize your gas costs you and your friends have compiled the following information.
First your car can reliably travel m miles on a tank of gas (but no further). One of your friends has mined gas-station data off the web and has plotted every gas station along your route along with the price of gas at that gas station. Specifically they have created a list of n+1 gas station prices from closest to furthest and a list of n distances between two adjacent gas stations. Tacoma is gas station number 0 and Tijuana is gas station number n. For convenience they have converted the cost of gas into price per mile traveled in your car. In addition the distance in miles between two adjacent gas-stations has also been calculated. You will begin your journey with a full tank of gas and when you get to Tijuana you will fill up for the return trip.
You need to determine which gas stations to stop at to minimize the cost of gas on your trip.
1. Express this problem formally with input and output conditions.
2. State a self-reduction for your problem.
3. State a dynamic programming algorithm based off your seld reduction that computes the minimum gas cost.