When transitions are lines
Some DP recurrences compute each entry as a minimum over earlier entries, where each candidate is a linear function of the current index. Written out, the transition looks like choosing the best line evaluated at a query point. Evaluating every candidate directly is slow.
The geometric idea
Each earlier state contributes a line with a slope and an intercept. The minimum of many lines at a query point lies on their lower envelope, a convex hull of lines. The convex hull trick maintains this envelope so each query finds the best line quickly.
- Insert lines as new states are computed.
- Query for the minimum at the current point.
- Discard lines that can never be optimal, keeping the envelope small.
When both insertion slopes and query points are monotonic, the envelope is maintained with a simple pointer or stack rather than a full search.
Key idea
The convex hull trick rewrites a DP transition as picking the best of many lines at a query point, maintaining their lower envelope so each transition is fast instead of scanning every candidate.