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?