You are driving from New York to Santa Clara. There are restaurants along the way you can eat at, and the cost of a meal at each restaurant is given. You must eat every 100 miles or less. So, you are given a list of pairs ((x1,c1), (x2,c2), …, (xn, cn)), where x is the distance from New York and c is the cost of a meal at the restaurant. If you decide to eat at a restaurant, you must eat the full meal and it will sustain you for the next 100 miles. Give a dynamic programming algorithm that finds where you should eat to spend the minimum amount of money, and, needless to say, make it to Santa Clara.
In your answer, explain how you initialize your table, and how at each step, you build and update the table.