We want to hike over a direct route from starting point $s$ to finish point $f$. We're given a list $p_1<p_2< \dots <p_n$ where the hotel at index $i$ is located $p_i$ kilometers from the start of the route. Throughout the travel we stop each night at a different hotel. The travel is time limited therefore we must finish the travel over $t$ days ($t<n$). The difficulty of walking a certain day is defined as $d^2$, the square of distance traveled.
We want to choose the stops in such a way that we minimize the sum of difficulty over the course of the travel (such that the overall difficulty is the lowest). Find the recurrence relation which describes the problem.
I encountered this problem in the context of dynamic programming. I don't understand how the problem can be described with a recurrence relation here.
This is a sample I drew:
For example we need to plan the travel for $2$ days. Then wouldn't we choose the distances from $p_1$ to $p_2$ and from $p_2$ to $p_3$ as they are minimal distances and hence will yield minimal squares?
Isn't this a matter of just sorting the distances and choosing $t$ minimal ones?
I observe that:
We can compute the minimal cost recursively on $t$, the number of remaining stops to make. Define $C(r,m)$ as the minimal cost of a trip that starts at hotel $m$ and visits $r$ different hotels, each with index $> m$.
We then have:
$C(r,m) = \min_{m<i< n-r} \left[ (p_i-p_m)^2 + C(r-1,i) \right]$ if $r>0$ and
$C(0,m) = (p_n - p_m)^2$ (to account for the last day, I assume $p_n$ represents $f$).
If we also define $p_0=0$, the desired answer is $C(t,0)$.