recognizing batchable transitions
A slow DP is usually slow for one specific reason: each state's transition does a lot of repeated work that overlaps with its neighbours' transitions. The skill of recognizing batchable transitions is the diagnostic eye that spots this overlap and asks 'can I compute these many similar transitions together, in a batch, instead of one painful scan at a time?' It is less a single algorithm than the meta-skill that tells you WHICH speed-up tool — prefix sums, monotonic structures, convex-hull trick, divide-and-conquer, Knuth's optimization — the problem is begging for.
The recognition works by looking at the shape of the inner loop, the part that makes dp[i] cost more than O(1). A few signatures recur. If dp[i] sums or takes a simple aggregate over a contiguous window of previous states, and consecutive i's windows mostly overlap, a prefix sum (or a sliding-window aggregate) batches them into O(1) each. If dp[i] is a min/max over earlier states where each contributes a linear function m_j * x + b_j of an index, that is the convex-hull-trick (or Li Chao) signature. If the transition is dp[i][j] = min over k of dp[i-1][k] + cost(k, j) and the best k is monotone in j, divide-and-conquer DP optimization applies; if the cost obeys the quadrangle inequality, Knuth's optimization narrows the interval search. The common thread: a naive transition recomputes, for each new state, an aggregate that barely changed from the previous state — so you maintain that aggregate incrementally instead.
Why this matters: the difference between an O(n^2) and an O(n log n) DP is often not a new recurrence but the same recurrence with a batched transition, and recognizing the pattern is what turns a too-slow correct solution into a fast one. The honest framing: each tool comes with preconditions (invertibility for prefix sums, monotone slopes or a Li Chao fallback for the hull, monotone optimal splits or the quadrangle inequality for the others), so recognizing the signature is step one and verifying the precondition is step two. Misreading the signature — applying the convex-hull trick when the contributions are not actually linear, or D&C optimization when the split is not monotone — produces fast, confidently wrong answers. The recognition is a hypothesis to be checked, not a license.
A DP with dp[i] = min over j < i of (dp[j] + (a[i] - a[j])^2) expands to dp[j] + a[j]^2 - 2 a[i] a[j] + a[i]^2. The terms in j form a line of slope -2 a[j] in the variable a[i] — that linear-in-the-query signature flags the convex-hull trick, turning an O(n^2) scan into O(n) or O(n log n).
Expand the transition algebraically; a linear-in-the-query term reveals which batch tool fits.
Recognizing a speed-up signature is a hypothesis, not a guarantee — each tool has preconditions (invertibility, monotone slopes, monotone splits, the quadrangle inequality). Apply one without checking its condition and you get a fast but wrong answer.