Pattern - Convex Hull Trick

Recognize CHT when:

$1.$ Your DP has $dp[i] = \min_j(f(j) \cdot g(i) + h(j))$ where $f$, $g$, $h$ depend only on their argument.

$2.$ The cost "mixes" $i$ and $j$ through a product term. Look for terms like $a_i \cdot b_j$ in the recurrence.

$3.$ You can rewrite as $\min_j(m_j \cdot x_i + c_j)$. Then check: Slopes $m_j$ monotonic? Use deque for inserts. Queries $x_i$ monotonic? Use deque for queries. Neither sorted? Use Li Chao tree instead.