Convex Hull Trick (CHT) DP Optimization
The Convex Hull Trick optimizes DP recurrences of the form dp[i] = min_j(m_j * x_i + c_j) from O(n^2) to O(n) or O(n log n) by maintaining the lower envelope of linear functions.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Convex Hull Trick (CHT) DP Optimization
When a 1D DP transition has the linear form:
$dp[i] = \min_{j < i} \Big( m_j \cdot x_i + c_j \Big)$
naive evaluation takes $O(n^2)$. Viewing each previous state $j$ as a line $y = m_j x + c_j$, the optimal transition at $x_i$ always lies on the lower envelope (convex hull of lines)! When slopes $m_j$ are monotonic and queries $x_i$ are monotonic, a deque maintains the lower envelope in $O(n)$ total time (and a Li Chao Tree or LineContainer handles arbitrary slopes/queries in $O(n \log n)$)!
Practice Problems
Hard
1. Monotonic Convex Hull Trick (Minimum Cost to Partition/Jump)
Maintain lines with strictly decreasing slopes m and answer minimum queries for increasing x in $O(1)$ amortized per line/query.
Approach: Pop the back line L2 when intersect(L1, L3) <= intersect(L1, L2) (so L2 is never optimal); pop the front line while L1(x) >= L2(x). Time: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <deque>
#include <iostream>
struct Line {
long long m, c;
long long eval(long long x) const { return m * x + c; }
};
// Returns true if line b is made obsolete by a and c (for decreasing slopes m)
bool bad(const Line& a, const Line& b, const Line& c) {
// (c.c - a.c) / (a.m - c.m) <= (b.c - a.c) / (a.m - b.m)
return static_cast<__int128>(c.c - a.c) * (a.m - b.m)
<= static_cast<__int128>(b.c - a.c) * (a.m - c.m);
}
struct MonotonicCHT {
std::deque<Line> dq;
void addLine(long long m, long long c) {
Line nl{m, c};
while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq.back(), nl)) dq.pop_back();
dq.push_back(nl);
}
long long query(long long x) {
while (dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x)) dq.pop_front();
return dq.front().eval(x);
}
};
int main() {
MonotonicCHT cht;
cht.addLine(-1, 10); // y = -x + 10
cht.addLine(-2, 14); // y = -2x + 14
cht.addLine(-4, 24); // y = -4x + 24
std::cout << cht.query(2) << " " << cht.query(5) << " " << cht.query(6) << "\n"; // 8 4 0
return 0;
}
</details>
---
Related Algorithms
- Knuth's DP Optimization — reduces $O(n^3)$ interval DP to $O(n^2)$.
- Convex Hull — geometric dual of the Convex Hull Trick.