Consider the following problem: You are on a road trip, and there are n cities a
ID: 647639 • Letter: C
Question
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 ai 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 a1,...,an.
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?
Explanation / Answer
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 ?(logn) 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.