Course contentsShow
← Computer Science
Lesson 958 of 2,87222. Dynamic ProgrammingFree lesson

Convex Hull Trick for DP

Optimize DP transitions involving linear functions using convex hull data structures.

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

  1. Represent each DP state as a line with slope and intercept derived from your recurrence
  2. Maintain a convex hull of these lines (lower or upper envelope depending on min/max)
  3. Query efficiently: for each new state, find the optimal line on the hull (binary search or amortized O(1) if queries are monotonic)
  4. 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.