What's Next

CHT optimizes DP with linear cost functions. But some DPs have range constraints: $j$ must be within a sliding window of $i$. Monotonic Queue improvement handles $dp[i] = \min_{j \in [i-k, i-1]}(dp[j]) + cost(i)$. The valid $j$ range slides with $i$.

Instead of a hull of lines, we maintain a deque of values. The front is always the best in the current window. Both are deque-based optimizations, but for different DP structures. Learn both to cover more problem types.