Pattern Guide
DP Optimized with Deque
"Sliding window DP: O(n²) → O(n). Deque maintains useful transitions."
Many O(n²) DP recurrences have the form dp[i] = min/max over j in [i-k..i-1] of (dp[j] + cost(j,i)). When only the range of j matters (not the specific index), use a monotonic deque to maintain the optimal j efficiently. Deque front = best j; pop front when out of window; pop back when current is better. Classic applications: jump game with window, maximize sum with constraint on window.
Problems you can solve with this pattern
4 problems · click any to start solving
// dp[i] = max dp[j] + val[i] for j in [i-k, i-1]
// Deque stores indices in window, front = index with max dp value
function slidingWindowDP(val, k) {
const n = val.length;
const dp = new Array(n).fill(0);
const deque = []; // indices, front = best (max dp)
for (let i = 0; i < n; i++) {
// Remove indices out of window [i-k, i-1]
while (deque.length && deque[0] < i - k) deque.shift();
// dp[i] = max dp[j] + val[i] for j in window
if (deque.length) dp[i] = dp[deque[0]] + val[i];
else dp[i] = val[i]; // no valid j
// Maintain monotonic deque: remove back if dp[back] <= dp[i]
// (i will be a better choice than those for future positions)
while (deque.length && dp[deque[deque.length-1]] <= dp[i])
deque.pop();
deque.push(i);
}
return Math.max(...dp);
}Sliding window DP pattern: dp[i] depends on dp[j] for j in some window [i-k, i-1]. Use a deque storing indices in the window. Deque is monotonic: front holds the optimal (min/max) j. When computing dp[i]: remove indices out of window from front; dp[i] = dp[deque.front] + cost; remove indices from back that are worse than i-1 for future i. Total: O(n).
// dp[i] = max dp[j] + val[i] for j in [i-k, i-1]
// Deque stores indices in window, front = index with max dp value
function slidingWindowDP(val, k) {
const n = val.length;
const dp = new Array(n).fill(0);
const deque = []; // indices, front = best (max dp)
for (let i = 0; i < n; i++) {
// Remove indices out of window [i-k, i-1]
while (deque.length && deque[0] < i - k) deque.shift();
// dp[i] = max dp[j] + val[i] for j in window
if (deque.length) dp[i] = dp[deque[0]] + val[i];
else dp[i] = val[i]; // no valid j
// Maintain monotonic deque: remove back if dp[back] <= dp[i]
// (i will be a better choice than those for future positions)
while (deque.length && dp[deque[deque.length-1]] <= dp[i])
deque.pop();
deque.push(i);
}
return Math.max(...dp);
}1. DP has form: dp[i] = min/max over j in window of (dp[j] + cost)
2. Window slides as i increases (old j's become invalid)
3. Deque maintains candidates with decreasing dp (for max) or increasing dp (for min)
4. Front of deque = optimal j; pop front when j < i-k
5. Pop back when new j is at least as good as back (monotone property)
Complexity: O(n) — each index pushed and popped from deque at most once.
Relation to convex hull trick: When cost(j,i) = linear function of j and i, use CHT or Li Chao tree instead. Deque works for window-only constraints.