Lessons from CHT

$1.$ CHT applies when the DP has form $dp[i] = \min_j(m_j \cdot x_i + c_j) + extra$.

$2.$ Rewrite your recurrence to extract the linear form. Identify $m_j$, $c_j$, $x_i$.

$3.$ Check if slopes or queries are sorted. If yes, use the simple deque. If not, use binary search or Li Chao tree.

$4.$ Time: $O(n)$

Time complexity: $O(n)$ for sorted case, $O(n \log n)$ for general case. CHT is effective because it doesn't require QI. It exploits linearity instead.

Space complexity: $O(n)$ for the hull.