AntInLoop

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