Monotone queue optimisation: a sliding minimum inside a DP

Why this matters when you build with AI

An AI tool will often write a DP that is correct and too slow. A common case: each state takes the best value over the last few states, and the tool loops over all of them. With a window of 20 this is fine. With a window of 20000 and n = 200000 it does 4 * 10^9 steps, and the judge stops the program.

The fix is usually a data structure that gives the window minimum in O(1) amortised time. The deque (double-ended queue: a list you can push and pop at both ends) is the simplest one for this job. A tool that knows the trick will still get the details wrong, for example by forgetting to drop indices that have left the window, or by dropping the wrong end. Those mistakes give answers that are too small and look plausible on the sample. This lesson shows how to check for them.

A prompt that asks for the trick and the proof, so a wrong invariant is easy to spot:

Write C++17 code for this problem. Input: n A B, then n costs c_1 to c_n.
Start at position 0. Choose positions 0 < p_1 < ... < p_m = n so every gap is between A and B.
Each chosen position i costs c_i. Print the minimum total cost, or -1 if no path exists.
Use a monotone deque, not a loop over the window. Before the code, state the invariant that the
deque keeps, say when an index is pushed, when it is popped from the back and when from the front,
and argue why each index is handled at most twice. Then show the output on the sample
"8 2 3" with costs "5 1 4 2 8 3 7 2". The output must be 8.

A good answer states the invariant (the deque values increase from front to back), gives the two pop rules, and prints 8. A bad answer pushes indices without popping, or never removes the indices that left the window. Check the answer by running it on random small inputs against a brute force (a method that tries every possibility, slow but easy to trust), as shown below.

Terms used

A window is the set of earlier indices a state is allowed to read. Here it is the indices j with i - B <= j <= i - A.
A sliding window is a window whose two ends move right as i grows.
The window minimum is the smallest stored value among the indices currently in the window.
A deque is a queue that also lets you push and pop at the front. The C++ type is std::deque.
Amortised cost is the average cost per operation over the whole run. One expensive step is allowed if the total stays small.
A brute force here means a loop over the whole window for every state. It is correct, and it is the reference for testing.

The idea: a DP whose window slides

Start with a small example. Take n = 8, A = 2, B = 3, and costs c = 5 1 4 2 8 3 7 2 for positions 1 to 8. Position 0 is the start and costs nothing. A valid path is 0, 2, 4, 6, 8. Its gaps are 2, 2, 2, 2, which all lie in [2, 3]. Its cost is c_2 + c_4 + c_6 + c_8 = 1 + 2 + 3 + 2 = 8. Another path is 0, 3, 6, 8 with gaps 3, 3, 2 and cost 4 + 3 + 2 = 9.

Let dp[i] be the cheapest cost of a path that ends exactly at position i. The last checkpoint before i is some j, and the gap i - j must lie in [A, B]. So j lies in the window from max(0, i - B) to i - A. The transition is:

dp[0] = 0
dp[i] = c_i + min(dp[j]) over j in [max(0, i - B), i - A]

If the window is empty, or every dp[j] in it is unreachable, then dp[i] is unreachable. The answer is dp[n], or -1 if it is unreachable.

Look at how the window moves. When i grows by 1, both ends grow by 1. The window is a block of fixed-looking width that slides right. This is the property that makes a deque work: an index that has left the window on the left never comes back, and an index added on the right is always newer than everything before it.

The naive code scans the window for every i. Its cost is the sum over i of the window width, about n * (B - A + 1) steps. With B - A = 20000 and n = 200000, that is 4 * 10^9 comparisons. The deque fixes this, as the next section shows.

Why the deque keeps the answer

Here is the key fact. Suppose two indices j1 < j2 are both in the window, and dp[j1] >= dp[j2]. Then j1 can never be the best choice again. Any future window that contains j1 also contains j2, because j2 is newer and the window only moves right. And j2 has a value that is no larger. So j1 can be thrown away.

The deque uses this fact. It keeps only indices whose values increase from front to back:

A new index j is pushed at the back. Before the push, every back entry with dp value >= dp[j] is popped, because by the fact above those entries are dead.
When the window's left end moves past an index, that index is popped from the front. It is the oldest entry, so it sits at the front if it is still there.
The window minimum is always at the front, because the values increase from front to back.

Two invariants follow. First, the values in the deque are non-decreasing from front to back. Second, every index that is still in the window and was not popped is in the deque, so the front is the true minimum.

Now run the sample by hand. The table below is the real output of the trace program on the sample. Each row is one value of i.

i  window     pushed  deque (index:dp)                 dp[i]
1  [0..-1]                                          INF
2  [0..0]   0       0:0                            1
3  [0..1]   1       0:0 1:INF                      4
4  [1..2]   2       2:1                            3
5  [2..3]   3       2:1 3:4                        9
6  [3..4]   4       4:3                            6
7  [4..5]   5       4:3 5:9                        10
8  [5..6]   6       6:6                            8

Read row i = 4. The window is [1..2]. Index 0 has left it, so it is popped from the front, and the deque holds only index 2 with dp 1. So dp[4] = 1 + c_4 = 1 + 2 = 3. Row i = 8 gives the answer: the window is [5..6], the deque front is index 6 with dp 6, and dp[8] = 6 + c_8 = 6 + 2 = 8, which matches the brute force.

The INF entry in row i = 3 is correct. Index 1 is unreachable, since one position with gap 1 from 0 is not allowed (A = 2). The deque keeps it because nothing newer had a smaller value yet, and it is never the front while a finite value is in the deque.

Proof that the run takes O(n) time

Count the work in two parts.

Each index j is pushed onto the deque exactly once. The loop while (nextPush <= hi) moves nextPush forward and never goes back, so there are at most n + 1 pushes in total.

Each index is popped at most once. An index leaves the deque either from the back (when a newer index with a value no larger arrives) or from the front (when it leaves the window). Once popped, it is gone and cannot be popped again. So the total number of pops is at most the number of pushes.

The while loops take time in proportion to the number of pops they perform. The total is therefore at most (n + 1) pushes plus (n + 1) pops, plus n constant-time reads for the front. That is O(n) in total. The average cost per index is O(1), which is what amortised means here.

One more check matters for correctness. The front pop uses the condition dq.front() < lo. It is safe because lo never decreases as i grows, so an index popped from the front can never be needed again.

Worked example: the full program

This is the complete program for the problem. It runs the deque version, prints dp[n], or -1 if the position is unreachable. It compiles with g++ -O2 -std=c++17.

// Lesson 07: checkpoints with allowed gaps, monotone queue optimisation.
// Positions 1..n each have a cost c[i]. Start at 0 (free). Choose checkpoints
// 0 < p_1 < ... < p_m = n so every gap p_k - p_{k-1} lies in [A, B].
// Each chosen position costs its c. Minimise the total. Print -1 if impossible.
// dp[i] = c[i] + min(dp[j] for j in [max(0, i-B), i-A]).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
 
// Reference version: scan the whole window for every i. O(n * (B - A + 1)) in the worst case.
vector<ll> solveNaive(int n, int A, int B, const vector<ll>& c) {
    vector<ll> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int hi = i - A, lo = max(0, i - B);
        ll best = INF;
        for (int j = lo; j <= hi; j++) best = min(best, dp[j]);
        if (best < INF) dp[i] = best + c[i];
    }
    return dp;
}
 
// Monotone queue: the deque holds indices j whose dp values increase from front to back.
// The front is always the window minimum. O(n) in total, each index is pushed and popped once.
vector<ll> solveDeque(int n, int A, int B, const vector<ll>& c) {
    vector<ll> dp(n + 1, INF);
    dp[0] = 0;
    deque<int> dq;
    int nextPush = 0;  // the next index j not yet added to the deque
    for (int i = 1; i <= n; i++) {
        int hi = i - A;          // newest index allowed in the window
        int lo = max(0, i - B);  // oldest index allowed in the window
        while (nextPush <= hi) {
            // Drop older entries that are not smaller than dp[nextPush]: they can never win again,
            // because nextPush is newer (it leaves the window later).
            while (!dq.empty() && dp[dq.back()] >= dp[nextPush]) dq.pop_back();
            dq.push_back(nextPush);
            nextPush++;
        }
        while (!dq.empty() && dq.front() < lo) dq.pop_front();  // left the window
        if (!dq.empty() && dp[dq.front()] < INF) dp[i] = dp[dq.front()] + c[i];
    }
    return dp;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, A, B;
    cin >> n >> A >> B;
    vector<ll> c(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> c[i];
    vector<ll> dp = solveDeque(n, A, B, c);
    cout << (dp[n] >= INF ? -1 : dp[n]) << "\n";
    return 0;
}

Run it on the three inputs below. The output is from the real build.

$ printf "8 2 3\n5 1 4 2 8 3 7 2\n" | ./solve
8
$ printf "4 2 3\n1 1 1 1\n" | ./solve
2
$ printf "5 3 3\n1 1 1 1 1\n" | ./solve
-1

The second case has the path 0, 2, 4 with cost 1 + 1 = 2. The third has no path, because 5 is not a sum of 3s.

How it was tested

The stress program compares three answers: a brute force that tries every subset of positions containing n, the naive window scan, and the deque. Its output on my machine:

exhaustive: 4000 cases ok, 3148 feasible
larger random: 3000 cases ok, all dp arrays equal

The first line used random n from 1 to 12, A from 1 to 4 and costs from 1 to 20. The second used n up to 400, windows up to 60 and costs up to 10^9. The second check compares the whole dp array, not only dp[n], so a wrong middle state cannot hide behind a correct final value. This is evidence on random inputs, not a proof of the code for every input. The proof is the invariant and the amortised count above.

How fast it is

Timings from the same machine as the other lessons in this module (12 hardware threads, Linux under WSL2, g++ 15.2.0, -O2). Your numbers will differ.

n	A	B	window	naive	deque
200000	1	5000	5000	479.3 ms	2.8 ms
200000	3	20000	19998	1736.7 ms	2.5 ms
200000	1	200000	200000	not run	3.3 ms

Both versions gave the same answer on each row that I ran both on. The naive time grows with the window width, and the deque time does not. The step count is the honest comparison: the naive loop does about n * window steps, the deque about 2n operations.

Common mistakes

Forgetting to pop from the front. The deque still holds an index that left the window, and its old value is used. The answer can then be too small, and it is wrong on some inputs only, so the sample may still pass.
Popping equal values from the back with > instead of >=. Both are correct for the answer. With >, equal values stay in the deque, so it is longer but still correct. Use >= and keep the reason in a comment.
Using a lower window bound that goes negative. Without max(0, i - B), the naive loop starts at a negative index and reads dp[-1], which is out of bounds and may crash or read garbage.
Not handling INF. If an unreachable state enters the deque at the front, every state after it becomes unreachable too. The check dp[dq.front()] < INF is needed, and an unreachable state must never be added to a sum (INF plus a cost can overflow).
Pushing an index before it is computed. The deque reads dp[j] when it pushes j. Push only indices up to hi = i - A, which are all earlier than i, so their dp values are already final.
Assuming the window is fixed width. The lower bound moves too, so an index can leave the window while newer ones are still arriving. The two while loops handle this, and removing either breaks the answer.

When the cost depends on j only

The form in this lesson adds c_i after the minimum. The standard form has the cost inside the minimum: dp[i] = min over j in the window of (dp[j] + g(j)), where g depends only on j. The same deque works. Store e[j] = dp[j] + g(j) when j is computed, and run the deque on e instead of dp. The invariant does not change, because it only uses the stored values.

If the cost depends on both j and i, for example the gap i - j, the deque no longer works directly, because the ordering of two candidates changes as i grows. Lessons 08 and 09 handle that case with lines and optimal split points.

Checklist

Write the window for i as [lo(i), hi(i)] and check that both ends never decrease as i grows.
Push every index up to hi(i) before reading the front.
Pop from the back while the new value is at most the back value, and from the front while the index is below lo(i).
Read the front only after the pops, and treat an INF front as unreachable.
Stress-test against a brute force on n up to about 12 with every subset, and then against the window scan on n up to a few hundred.
Time the naive version and the deque on the largest n and widest window your limits allow.

Summary

A DP whose transition takes the minimum over a sliding window can use a deque that keeps indices with increasing values. Each index is pushed and popped at most once, so the run is O(n). The deque is correct only if you pop from the back on dominated values and from the front on indices that left the window, and if you handle unreachable states. Test against brute force before you trust it.

Practice

Take n = 5, A = 2, B = 2, costs 1 2 3 4 5. Predict the output of the program before you run it. Then run it. Hint: think about which positions a path can visit with gaps of exactly 2 from 0.

Show the answer

The output is -1. Gaps must be exactly 2, so a path visits 0, 2, 4, and then 6, which is past n. Position 5 cannot be reached from any earlier position, because 5 minus 2 is 3, and 3 is not reachable from 0 with gaps of 2.
The cost is g(j) inside the minimum, not c_i outside. Rewrite the transition so the same deque code works, and say which array the deque stores. Hint: a stored value can already include the term for j.

Show the answer

Store e[j] = dp[j] + g(j) once dp[j] is final, and set dp[i] = min over the window of e[j]. The deque now holds indices with increasing e values, and the window rule is unchanged. Only the value array that the deque compares changes.
Explain, without code, why the front pop must test dq.front() < lo and not dq.front() <= hi. Hint: hi is the newest allowed index, and lo is the oldest allowed index.

Show the answer

An index below lo is too old for the current window. An index at or below hi is already in the window or older, and popping on hi would delete valid candidates. The front pop must remove exactly the indices that are older than the window's left end.
Make a test where a deque implementation without the back pop (only the front pop and a plain push) gives a wrong answer, and say what the wrong value is. Hint: the wrong answer should come from an old index that is smaller than a newer one but still in the deque.

Show the answer

Without the back pop, the deque keeps entries whose values are not in increasing order, so the front is not the window minimum. Input 7 2 3 with costs 13 6 3 5 20 20 15 shows it. The deque gives 26, and the version without the back pop gives -1, so it misses a path that exists. This was found by comparing the two programs on 3000 random small inputs; the first mismatch is this one.