7
$\begingroup$

Consider the following problem:

You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between two adjacent cities is one mile. We are currently at city $1$, and would like to drive to city $n$. Each day, we can drive at most $k$ miles, before we sleep for the night. We pay $a_i$ for lodging at the city located at mile $i$. Each lodging cost is a positive number. Given that we can spend an arbitrary number of days on the road trip, determine a plan of driving to minimize lodging costs.

Input: An integer $k$, and a length $n$ array of positive integers $a_1,...,a_n$.

Output: The minimum lodging cost to complete the road trip starting from city 1 and ending at city n.

The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?

Improve this question
$\endgroup$
9
  • $\begingroup$ Since $k$ is part of the input, the complexity is actually $O(n^2)$. $\endgroup$
    – Yuval Filmus
    Commented Mar 20, 2015 at 3:27
  • $\begingroup$ Do you have more than an intuition? Does the exercise call for a better running time? Otherwise, I see no reason why you could improve on $O(n^2)$ substantially. $\endgroup$
    – Yuval Filmus
    Commented Mar 20, 2015 at 3:28
  • $\begingroup$ The exercise does suggest that it is achievable in $O(n)$ time. However, I'm struggling to see how it can be done. $\endgroup$
    – Dave
    Commented Mar 20, 2015 at 3:58
  • $\begingroup$ You can try other popular paradigms such as greedy and divide and conquer. $\endgroup$
    – Yuval Filmus
    Commented Mar 20, 2015 at 6:26
  • $\begingroup$ @YuvalFilmus means to use $\Theta$ there. I don't see how even $O(n^2)$ is correct, though; $k$ is a number so $\Theta(nk)$ is pseudopolynomial, far away from linear time. $\endgroup$
    – Raphael
    Commented Mar 20, 2015 at 6:58

1 Answer 1

Reset to default
6
$\begingroup$

This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.