n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly
d days (i.e have to make
d-1 stops in between). If you travel
x miles during a day, the cost for that day is
x^2. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.
I came up with this dp solution:
dp(i) be the minimum cost such that the last stop is hotel i.
To compute dp(i), I consider all possible places
0<=k<i, that we might have stopped before. Thus, the recurrence relation becomes:
for i=1;i<=n;i++ dp(i)=inf prev(i)=undefined for k=0;k<i;k++ if (dp(i)>dp(k)+(ai-ak)^2) dp(i) = dp(k)+(ai-ak)^2) prev(i) = k
How do we make sure that this algorithm takes exactly d stops?