Lessons from Constrained Sum

What did you learn?

$1.$ When DP transitions look at the last $k$ states, monotonic deques can optimize from $O(nk)$ to $O(n)$.

$2.$ You've learned a general pattern. Any DP where you need $\max$ or $\min$ over a sliding window of previous states can use this technique.

$3.$ The deque stores indices into the DP array, ordered by DP values. This optimization appears in advanced DP problems. Recognize the pattern: "max/min over previous $k$ states."