Pattern - CHT Recognition

Signal: $dp[i] = \min_{j}(dp[j] + f(i, j))$ where $f(i, j)$ can be written as $m_j \cdot g(i) + c_j + h(i)$. The $m_j \cdot g(i)$ is the linear term. $c_j$ is the intercept. $h(i)$ is added after the query.

Common forms: $a_j \cdot b_i$, $(a - b)^2$ expanded, prefix sum products. Look for products of $i$-term and $j$-term. If you see a quadratic that expands into separable terms, CHT likely applies. Practice recognizing the pattern.