Dynamic Programming • Optimization

Convex Hull Trick

Optimize DP transitions of the form `dp[i] = min(dp[j] + m[j]*x[i] + c[j])` from O(N^2) to O(N) or O(N log N).

Overview

When computing the minimum of several linear functions `y = mx + c` evaluated at `x`, we only need to keep track of the lower envelope of these lines.

Line Elimination

If line L2 is intersected by line L3 before L2 intersects L1, then L2 is "swallowed" by L1 and L3, meaning L2 is never the strict minimum at any `x`. It can be removed.

Stack Maintenance

We maintain a stack of active lines (the hull). When adding a new line (sorted by slope), we pop lines from the end of the stack if they become redundant.

Key Insight

By discarding redundant lines, we drastically reduce the search space. We can then query the optimal line for any `x` using binary search or a monotonic pointer.

Code Tracker

:::

1let hull = [];

2for (let l of sortedLines) {

3 while (hull.length >= 2) {

4 let l1 = hull[hull.length - 2];

5 let l2 = hull[hull.length - 1];

6 let x12 = (l2.c - l1.c) / (l1.m - l2.m);

7 let x23 = (l.c - l2.c) / (l2.m - l.m);

8 if (x12 >= x23) hull.pop();

9 else break;

10 }

11 hull.push(l);

12}