A Different Pattern

In the previous section, you learned that Quadrangle Inequality (QI) improvement works when optimal splits are monotonic. But what if your cost function doesn't satisfy QI? Consider $dp[i] = \min_{j < i}(dp[j] + (s_i - s_j)^2)$ where $s$ is a prefix sum.

Expanding: $dp[i] = \min_j(dp[j] + s_i^2 - 2s_i s_j + s_j^2)$. The term $-2s_i s_j$ mixes $i$ and $j$. This isn't QI-friendly. But look closer: for fixed $i$, this is linear in $s_j$. That's the pattern CHT exploits.