Monotone Queue Optimization

Optimise a DP whose transition is a minimum or maximum over a sliding window:

$dp[i]={\min }_{i-k\le j<i}dp[j]+\mathrm{cost}(i)$

from $O(nk)$ to $O(n)$, using a monotonic deque.

The sliding window minimum

Keep a deque of indices whose dp values are increasing. Before pushing $i$, pop everything at the back with a value $\ge dp[i]$ — those can never be the minimum again, because $i$ is both newer and better. Before querying, pop the front while it has fallen out of the window.

deque<int> dq;
for (int i = 0; i <= n; i++) {
    while (!dq.empty() && dq.front() < i - k) dq.pop_front();     // out of window
    dp[i] = (i == 0) ? 0 : dp[dq.front()] + cost(i);
    while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();  // dominated
    dq.push_back(i);
}

Each index enters and leaves the deque once, so the total work is $O(n)$.

When the window is not a fixed width

The technique needs only that the valid range of $j$ is a contiguous interval that moves monotonically with $i$. Common cases:

Condition on $j$	Window
$i-k\le j<i$	fixed width $k$
$\mathrm{pref}[i]-\mathrm{pref}[j]\le W$	two pointers determine the left end
$a_i-a_j\le D$ (sorted $a$)	two pointers
$j\ge \mathrm{lastBad}[i]$ where lastBad is non-decreasing	two pointers

If the left end can move backwards, the deque is invalid — use a segment tree ($O(n\log n)$) or a different optimisation.

Adding a term that depends on $j$

If the transition is $dp[i]={\min }_j(dp[j]+f(j))+g(i)$, store $dp[j]+f(j)$ in the deque instead of $dp[j]$. The deque only needs the quantity being minimised to be computable at push time.

If instead the term couples $i$ and $j$ multiplicatively, the deque fails and you want CHT:

Transition shape	Technique
${\min }_{j}dp[j]$ over a window	monotone queue, $O(n)$
${\min }_j(dp[j]+f(j))$ over a window	monotone queue, $O(n)$
${\min }_j(dp[j]+m_j{x}_i)$	CHT
${\min }_j(dp[j]+C(j,i))$, $C$ Monge	D&C DP
${\min }_{j}dp[j]$ over an arbitrary range	segment tree, $O(n\log n)$

Classic uses

Jump game with a bounded jump. dp[i] = min(dp[j]) + cost(i) for $j\in [i-k,i-1]$ — the textbook case.

Bounded knapsack in $O(nW)$. Group weights by residue class mod $w{t}_i$; within each class the transition is a sliding-window maximum of $dp[w-t\cdot w{t}_i]-t\cdot va{l}_i$ over $t\in [0,c_i]$. This is how bounded knapsack achieves $O(nW)$ instead of $O(nW\log c)$ — see Knapsack.

Maximum subarray with a length limit. max(pref[i] - min(pref[j])) over a window.

Constrained partitioning. “Split the array into pieces of length between $a$ and $b$, minimising the total cost” — the window is $[i-b,i-a]$.

The standalone structure

Sliding window minimum is useful outside DP too — see Monotonic Queue. It is also the $O(1)$-amortized way to implement a minimum queue, which is what makes Mo’s algorithm variants and certain graph algorithms fast.

Debugging checklist

1. Is the window’s left end monotone non-decreasing? If not, the deque is wrong.
2. Are you popping the front before querying and the back before pushing?
3. Is the comparison >= (keeping the newest among equals) rather than >? Either is correct for the value, but >= keeps the deque shorter.
4. Is dp[i] pushed after it is computed? Pushing before creates a self-dependency.

See also: Monotonic Queue · Convex Hull Trick · Knapsack