the convex-hull trick
Some DP transitions look like dp[i] = min over j < i of (a line evaluated at x_i): each earlier state j contributes a straight line m_j * x + b_j, and to compute dp[i] you ask 'among all these lines, which gives the smallest value at the query point x = x_i?' Evaluating every line for every i is O(n^2). The convex-hull trick speeds this up by noticing that, at any query point, the minimum over a set of lines is given by the lower envelope of those lines — a piecewise-linear convex shape — and most lines never matter because they are above the envelope everywhere.
Picture each candidate as a line on a graph. The lower envelope is the boundary you would see looking up from below: for each x, the lowest line. Lines that are nowhere the lowest can be discarded entirely. The trick maintains only the lines forming this envelope (it is the lower convex hull of the lines, hence the name), in order of slope. To find the minimum at a query x, you binary-search the envelope for the segment covering x, in O(log n). When the query points arrive in sorted order and lines are added in sorted slope order — which is common in DP — you can use a monotonic stack and a moving pointer to make adds and queries amortized O(1), giving an O(n) or O(n log n) DP. Adding a new line pops lines from the hull that it makes redundant, just like building a convex hull with Graham scan.
This turns an O(n^2) DP into O(n log n) (sorted, with binary search) or O(n) (fully monotone) for transitions of the line-minimum form — a standard speed-up for problems where the cost factors into a slope-times-x plus an offset, such as certain partitioning and scheduling DPs. The honest constraints: the basic version requires the lines to be inserted in monotone slope order and (for the O(1) query) the x-queries to be monotone too; violate either and you must sort, use a balanced structure, or switch to a Li Chao tree, which handles arbitrary insertion and query order at O(log range) each. Also, you must keep straight whether you are taking a min (lower envelope) or a max (upper envelope) — they are mirror images and mixing them up is a classic bug.
dp[i] = min over j of (dp[j] + b[j] * a[i]). Treat each j as a line y = (b[j]) * x + dp[j] queried at x = a[i]. Most lines never give the minimum at any x and are pruned from the lower envelope. If the a[i] are increasing and slopes b[j] decreasing, a monotonic stack answers each query in amortized O(1), so the whole DP is O(n).
The minimum of many lines lives on their lower envelope; off-envelope lines are dead weight.
The fast O(1) version assumes monotone slopes AND monotone queries; lose either and you must binary-search, sort, or use a Li Chao tree. And min uses the lower envelope while max uses the upper — never confuse the two.