You are going on a trip from point $s$ to point $f$, in the way there are $n$ hotels, $p_1, p_2,..., p_n$ each denotes the number of $km$ from $s$. You must complete the trip by at most $t$ days ($t<n$) while stopping at one of the hotels each night. The cost of each day is $d^2$, where $d$ is the number of $km$ traveled on that day. Develop an algorithm to find the subset of hotels that minimize the trip cost
I came up with the following dynamic programming solution:
define array $M_{n\times t}$ such that $M(i, j)$ represents the cost of reaching hotel $i$ in $j$ days
foreach $(i, j) \in n\times j$ if $i < j$ do $M(i, j)\leftarrow \infty$ endforeach
for $i \leftarrow 1$ to $n$ do $ M(i, 1) \leftarrow i$ endfor
for j <- 2 to t do
for i <- j to n do
min <- infinity
for k <- 1 to i-1 do
if M(k, j-1) + (d_i - d_k)^2 < min do M(i, j) <- M(k, j-1) + (d_i - d_k)^2 endif endfor endfor endforreturn $min_{1\le j \le t}(M(n, j))$
As for efficiency, initializing $M$ in steps 2 and 3 is done in $O(n)$ and updating the rest of $M$ is done in $O(n^2t)$, and step 5 is done in $O(t)$, so all in all time complexity of my solution is $O(n^2t)$ and space complexity of $O(nt)$.
Can I improve this? i.e have a solution with $O(nt)$ time complexity? I tried to use the Knapsack problem as a guide, because I know it can be solved in $O(nt)$, but I always end up with $n^2$ loop
