Monotone Queue Optimization
Speed up DP transitions over a sliding range by keeping only the best candidates in a deque.
Monotone Queue Optimization
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Monotone queue optimization is a DP speedup for transitions that ask for the minimum or maximum over a sliding window of previous states. Instead of scanning that window every time, a deque keeps only the candidates that can still win in the future.
When to Use It
Use it when:
the transition is \(\min\) or \(\max\) over a contiguous range of previous indices,
the valid range slides forward as the current index increases,
the value compared inside the transition can be maintained in monotone order.
Core Idea
Suppose \[ dp[i] = a[i] + \min_{i-k \le j < i} dp[j]. \] As \(i\) moves right, the allowed range of \(j\) also moves right. A deque can store candidate indices in increasing order of their DP values while discarding:
indices that leave the range,
indices whose value is dominated by a newer candidate.
Key Insight
If a newer index has a DP value no worse than an older one, and it will remain valid at least as long, the older one can never become optimal again. That is what makes the deque small.
Operations / Main Technique
pop from the front while an index is out of range,
use the front as the best candidate,
pop from the back while the new value dominates older candidates,
push the current index.
Worked example.
If the deque stores candidate DP values \([5, 7, 9]\) and the new state has value \(6\), then \(7\) and \(9\) are removed from the back because they will never beat \(6\) in any future window where \(6\) is still present.
Correctness Intuition
The deque remains ordered by increasing candidate value, so its front is always the best valid transition source. The domination rule is safe because any removed candidate is worse than a newer one and expires no later.
Complexity Analysis
Each index enters and leaves the deque at most once, so the optimized transition runs in \(O(n)\) total time.
Implementation
The sample code solves the sliding-window minimum DP pattern directly. In practice, many problems reduce to that form after algebraic cleanup of the transition.
Common Pitfalls
Applying the trick when the valid transition range is not contiguous.
Forgetting which transformed value should be monotone in the deque.
Off-by-one mistakes in the window endpoints.
Variants / Extensions
Sliding-window maximum by reversing the comparisons.
Deque optimization after subtracting a linear term from the transition.
Comparison with convex hull trick when the dependence is linear instead of window-based.
Practice Problems
DP with a bounded jump length.
Minimum-cost path with moves limited to the last \(k\) states.
Sequence partition problems reducible to sliding minima.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<long long> dp_sliding_window_min(const vector<long long>& add, int k) {
int n = (int)add.size();
const long long INF = (long long)4e18;
vector<long long> dp(n, INF);
deque<int> dq;
dp[0] = add[0];
dq.push_back(0);
for (int i = 1; i < n; ++i) {
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
dp[i] = dp[dq.front()] + add[i];
while (!dq.empty() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.