DP with Monotonic Queues

A monotonic deque can optimize a DP whose best predecessor lies in a sliding index window. We minimize landing cost when each jump advances between 1 and K positions. The direct recurrence scans up to K earlier states per position; the deque retains only nondominated candidates and removes those that expire. The proof depends on both value dominance and monotone expiration.

Prerequisites: One-Dimensional DP; Monotonic Queues; amortized analysis. Related existing lessons: Monotonic Queues.

Build the idea

1. Recognize the repeated subproblems

   Line-position DP already merges histories, but n states with K predecessors still cost O(nK). If each predecessor contributes its fixed dp value plus a term depending only on the destination, and eligibility is a sliding window, the minimum can be maintained dynamically. Arbitrary pair-dependent costs or nonmonotone eligibility do not permit the same deque rule.

2. Define the state

   dp[i] is minimum cost from zero to position i, paying cost[i] on arrival. Eligible predecessors are j∈[max(0, i−K), i−1]. The deque stores candidate indices in increasing time order and strictly increasing dp value after equal-or-worse old tails are removed. Its front is therefore the minimum-valued unexpired predecessor.

3. Derive the transition

   Before computing i, remove front indices< i−K. Set dp[i]=cost[i]+dp[front]. Then remove back indices with value≥dp[i] and append i. A newer no-more-expensive state expires later than an older one, so it dominates that older state for every future query where the older would remain eligible. This independence from destination is the crucial optimization condition.

4. Base cases and computation order

   dp[0]=0 and the deque begins with index 0. Process i increasingly. Query before inserting i so the transition cannot use itself. K≥1 guarantees i−1 is a legal predecessor, so an unexpired candidate always exists. Negative costs are allowed because jumps move forward and no cyclic improvements occur. Only the minimum value is output, no parent chain is kept.

5. Correctness and invariant

   Inductively, the deque omits only expired states or states dominated by a newer candidate with no larger value. Removing dominated candidates cannot lose any future optimum, and removing expired ones enforces the index window. The front yields exactly the direct recurrence’s minimum. Each index enters once and leaves at most once from each end, so the while loops are amortized linear rather than nested quadratic work.

6. Work the example

   For K=2, costs [5,1,4,−2,3], dp values are [0,5,1,5,−1,2]. At i=4, the predecessor window is indices 2,3 with values 1,5, so the answer becomes −1. That new state dominates older costlier candidates and later gives dp[5]=2. Expiration prevents the old zero state from being used beyond its allowed reach.

   i	0	1	2	3	4	5
   dp	0	5	1	5	-1	2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<deque>
int main(){
    int n,K;
    std::cin>>n>>K;
    std::vector<long long>dp(n+1);
    std::deque<int>candidate{0};
    for(int i=1;i<=n;++i){
        long long cost;
        std::cin>>cost;
        while(candidate.front()<i-K){
            candidate.pop_front();
        }
        dp[i]=cost+dp[candidate.front()];
        while(!candidate.empty()&&dp[candidate.back()]>=dp[i]){
            candidate.pop_back();
        }
        candidate.push_back(i);
    } // A newer no-worse state expires later, so it dominates the old one.
    std::cout<<dp[n]<<'\n';
}

Complexity analysis

Direct DP has n states and≤K transitions each:O(nK). The deque reduces total candidate maintenance/query work to O(n) amortized. The shown dp vector uses O(n) space; the deque has O(K) live candidates, and a value/index-only variant can reduce total working DP storage to O(K).

Example input and output

Read n K (1≤K≤n≤200000), then n landing costs within ±10^9. Jumps from zero advance 1..K positions. Print minimum landing cost to n.

Input

5 2
5 1 4 -2 3

Output

2

For K=2, costs [5,1,4,−2,3], dp values are [0,5,1,5,−1,2]. At i=4, the predecessor window is indices 2,3 with values 1,5, so the answer becomes −1. That new state dominates older costlier candidates and later gives dp[5]=2. Expiration prevents the old zero state from being used beyond its allowed reach.

Practical applications

Use for sliding-range min/max transitions with separable destination terms. Monotonic Queues in Data Structures explains the container invariant; here it accelerates a recurrence. More general affine transition dependence leads toward convex hull trick rather than this simple minimum deque.

Check your understanding

Why can a newer state with no larger dp remove an older candidate?

Put it into practice

Compare every state with a direct K-predecessor scan.