Does anyone know how to answer this problem? I have been stuck for a few days trying to figure it out.
A students decides to ride her bicycle from Vancouver to Halifax. She starts on the road at kilometer 0. Along the way there are n hotels H1, . . . , Hn, at distances h_1 < h_2 < h_3 < . . . < h_n−1 < h_n from the trip’s starting point respectively. The only places where the student is willing to stop for the night are these hotels, but she can choose which hotels she stops at. She must stop at the final hotel H_n since this is her destination (she is planning on flying back). Ideally, this student would like to travel 100Km per day, but this may not be possible, depending on the spacing of the hotels. In order to determine how close the student got to this target distance, she defines the penalty for a day to be |100 − x|^1.5 where x is the distance traveled that day. Her objective is to plan her trip in a way that minimizes the sum of the daily penalties over all days of the trip.
- Write a recurrence relation for D_k, where D_k is the minimum sum of the daily penalties, over all possible trips that end at hotel H_k (that is, the student does not go any further)
- Find a dynamic programming algorithm that computes D_n.
I think the best way to think about this problem is to think backward. Lets say you are at Hotel N, what was the last optimal last? Was it n-1? n-2? n-3?. Then, you pick the best and work backward until to get to the starting point