# How to find minimal distances route for a trip of $t$ days, given distances for each stop?

We want to hike over a direct route from starting point $$s$$ to finish point $$f$$. We're given a list $$p_1 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). 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?

• Don't you need to get to the finish point too? – user856 Feb 3 '18 at 9:57
• @Rahul I think I see now. So wouldn't this be a variation of knapsack problem where we want minimum instead of maximum? – Yos Feb 3 '18 at 10:00

I observe that:

1. you are required to stay at a different hotel for $t$ nights and
2. it never makes sense to go backwards.

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)$.

• But the recursion should probably be reversed to decrease complexity :) – Fons Feb 11 '18 at 17:35
• I think the idea is right, but I don't follow the formulas. It seems to me that you should be minimizing over $m < i < n-r,$ because hotel $i$ is the next hotel to visit after hotel $m$ and there must be at least $r-1$ hotels remaining after hotel $i$. I also think you mean $C(r,m)$ to be the cost of completing the journey starting at hotel $m$ in $r$ days. You say "visiting hotels with index $\ge m$" but you must mean "index > $m$" or the term $(p_i-p_m)^2$ makes no sense. – saulspatz Feb 11 '18 at 18:39
• You are right! The case C(0,m) should also be defined separately to make sure that the goal is reached. – Fons Feb 12 '18 at 20:58
• I am also assuming that all $p_i$'s are non-negative. – Fons Feb 13 '18 at 11:38