Dynamic Programming formulation for hotel problem There are n hotels given at a0, a1, ..., an such that 0 &lt; a0 &lt; a1 &lt; ... &lt; 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:

Let dp(i) be the minimum cost such that the last stop is hotel i.
Base case: dp(0)=0.

To compute dp(i), I consider all possible places 0&lt;=k&lt;i, that we might have stopped before. Thus, the recurrence relation becomes:

for i=1;i&lt;=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k&lt;i;k++
    if (dp(i)&gt;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?
Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases: 

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a_n / d$ miles every day. 

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey. 

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a_i^2 \space/\space j\space+\space(a_n - a_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead. 

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.