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:

  1. define array $M_{n\times t}$ such that $M(i, j)$ represents the cost of reaching hotel $i$ in $j$ days

  2. foreach $(i, j) \in n\times j$ if $i < j$ do $M(i, j)\leftarrow \infty$ endforeach

  3. for $i \leftarrow 1$ to $n$ do $ M(i, 1) \leftarrow i$ endfor

  4. 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 endfor

  5. return $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

  • $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Commented May 30, 2022 at 2:10
  • $\begingroup$ @D.W. I'm not sure what you are referring to, the question was written on the board in my class, I copied it to my notebook, and translated it to English to be posted here. The algorithm itself, I came up with on my own based on an example of the subset-sum problem from "Algorithm Design" by Jon Kleinberg, Eva Tardos $\endgroup$ Commented May 30, 2022 at 7:19
  • $\begingroup$ Great, you should be able to credit the instructor who wrote the assignment on the board, then! It may also be helpful to tell us what topics you are studying right now. $\endgroup$
    – D.W.
    Commented May 30, 2022 at 17:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.