Pattern Reference
DP with Deque Optimization
"Sliding window DP optimization: DP[i] = max over j in window of DP[j] + f(j,i). Range min/max of DP values."
Loading...
Deep Dive Tutorial
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).
Sliding window DP template with deque
// 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);
}Worked Problems
rocket
Deque DP optimization checklist:
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.
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.