When a dynamic programming recurrence has the form $dp[i] = min_{j < i} (dp[j] + m_j cdot x_i + c_j)$, each candidate $j$ represents a linear equation $y = m_j x + k_j$. The Convex Hull Trick maintains the lower envelope of these lines to query optimal values in $O(log N)$ or amortized $O(1)$ time.
1. Monotonic Slope Deque Optimization
If slopes $m_j$ and query coordinates $x_i$ are monotonically ordered, we can maintain the convex hull lines in a double-ended queue, pruning suboptimal lines from the back when their intersection point with previous lines is dominated.