Convex Hull Trick for DP
What you'll learn: How to speed up certain dynamic programming transitions from O(n²) to O(n log n) or even O(n) by exploiting the geometry of linear functions.
The Core Idea
Some DP problems require you to compute transitions like:
dp[i] = min(dp[j] + cost(j, i)) for all j < i
When cost(j, i) can be expressed as a linear function of j (something like A[j] * B[i] + C[j]), you're essentially choosing the minimum among many lines evaluated at a point. Instead of checking all previous states (O(n) per state → O(n²) total), you can maintain a convex hull of these lines.
Think of it like this: imagine each previous state j defines a line y = mx + b. For a fixed x (your current position i), you want the line with the minimum (or maximum) y value. Most lines are irrelevant—they're "hidden" behind better ones. The convex hull trick maintains only the "frontier" of useful lines.
How It Works
- Represent each DP state as a line with slope and intercept derived from your recurrence
- Maintain a convex hull of these lines (lower or upper envelope depending on min/max)
- Query efficiently: for each new state, find the optimal line on the hull (binary search or amortized O(1) if queries are monotonic)
- Add new lines while preserving convexity (remove dominated lines)
This transforms O(n²) into O(n log n) with binary search queries, or O(n) when slopes and queries are monotonic.
Key Takeaway: The Convex Hull Trick optimizes DP transitions involving linear functions by maintaining only the envelope of relevant lines, reducing complexity from quadratic to linearithmic or linear time.