# Solving road trip problem in linear time

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?

• Since $k$ is part of the input, the complexity is actually $O(n^2)$. – Yuval Filmus Mar 20 '15 at 3:27
• 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. – Yuval Filmus Mar 20 '15 at 3:28
• The exercise does suggest that it is achievable in $O(n)$ time. However, I'm struggling to see how it can be done. – Dave Mar 20 '15 at 3:58
• You can try other popular paradigms such as greedy and divide and conquer. – Yuval Filmus Mar 20 '15 at 6:26
• @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. – Raphael Mar 20 '15 at 6:58

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.