When the state is right but the transition is slow
By now you can read a problem, name its progress counters, and write the transition. But a correct DP can still be too slow, and the culprit is almost always the same: the table has a reasonable number of cells, yet computing one cell scans a whole range of earlier cells. If there are n states and each does O(n) work to fill, you pay O(n^2) — fine for n in the thousands, painful past a hundred thousand. The fix is rarely a new state; it is making each transition cheaper by not redoing work you already did. This guide collects the standard tools for exactly that, the same speed-up toolkit promised at the top of this rung.
Keep one honest caveat in mind throughout. Big-O hides constants and low-order terms, so an O(n log n) speed-up describes how the cost scales, not a guarantee that it wins at every size. The plainer O(n^2) loop, with its tiny constant and friendly memory access, can beat a clever O(n log n) method for small n — sometimes for surprisingly large n. So measure before you reach for machinery: these tricks earn their keep when n is genuinely large or the transition is genuinely the bottleneck, not as a reflex.
Prefix sums: pay once, answer many
The humblest speed-up is also the most common. Suppose a transition needs the sum of array values over a range, like dp[i] depending on (sum of a[l..i]) for many choices of l. Recomputing each sum from scratch is O(range) per query. Instead build a prefix-sum array once: P[0] = 0 and P[k] = P[k-1] + a[k]. Now the sum of any range a[l..r] is just P[r] - P[l-1], a single subtraction in O(1). You spent O(n) up front so that thousands of later range questions each cost a constant. This is the cleanest case of the prefix-sum speed-up: precompute the cumulative work, then answer windows in O(1).
P[0] = 0 for k = 1..n: P[k] = P[k-1] + a[k] # O(n) once range_sum(l, r) = P[r] - P[l-1] # O(1) each query
The pattern reaches well past plain sums. Counting DPs often need "how many ways land in window [l, r]?", which is a prefix sum over the count table; expectation DPs need range averages, which are prefix sums divided by length. In interval problems like the matrix-chain and other interval DPs from earlier in this rung, the cost of merging a range a[i..j] is frequently a fixed function of P[j] - P[i-1], so prefix sums let each of the O(n^2) intervals price its split points without re-scanning. The mental move is always the same: spot a quantity asked over many overlapping ranges, and pay for it once.
The convex-hull trick: transitions that are lines
Now a deeper idea for a very common shape. Many DPs have a transition of the form dp[i] = min over j < i of ( dp[j] + b[j] * x[i] + c[i] ). Hold i fixed and look at the part inside the min: for each earlier j it is dp[j] + b[j] * x[i], which as a function of the query value x[i] is a straight line — slope b[j], intercept dp[j]. So filling cell i asks: among a set of lines, which one is lowest at the point x = x[i]? Computing dp[i] by scanning all j is O(n) per cell and O(n^2) overall. The convex-hull trick answers that "lowest line at a point" query far faster.
Here is why a hull appears. Take the lower envelope of all the lines — at every x, the smallest y any line achieves. A line that is never the minimum anywhere (it sits above some combination of two others across the whole range) can be thrown away forever; it can never win a query. The lines that survive, ordered by slope, form a sequence whose envelope is a piecewise-linear convex curve — the same lower-convex-hull shape from computational geometry, now living in the space of (slope, intercept) instead of (x, y). Only the hull lines matter, and they are sorted, so a query becomes a search instead of a scan.
- Read the transition dp[j] + b[j] * x[i] as a line: slope b[j], intercept dp[j]; the query point is x[i].
- Maintain the lower envelope (the convex hull) of all lines added so far, keeping only lines that win somewhere.
- When adding a new line, pop hull lines that are now made redundant by the newcomer — each line is added once and removed at most once.
- To compute dp[i], query the hull for the lowest line at x = x[i] — by binary search, or a moving pointer if queries are sorted.
The cost depends on how tame the inputs are. In the friendliest case — the slopes b[j] are added in sorted order and the query points x[i] are also sorted — the whole envelope is maintained with two monotonic pointers, every line is pushed and popped at most once, and the total is O(n). That popping argument is genuine amortized analysis: a single insertion might remove many lines, but across the whole run no line can be removed more than once, so the average over the sequence is O(1) — even though one particular step is not. If slopes or queries arrive in arbitrary order you keep the hull in a balanced structure and binary-search each query, giving O(n log n); the Li Chao tree is a clean alternative that handles arbitrary lines and queries directly.
Other ways to batch a transition
The convex-hull trick is one member of a family: methods that exploit hidden structure in a transition so that the best split point for one state helps locate it for the next. Divide-and-conquer DP optimization applies when the optimal split index is monotone — as the state grows, its best choice never moves backward. If opt(i) <= opt(i+1) always, you can solve the states in a divide-and-conquer order, computing the middle state's optimum first and using it to shrink the search interval for the halves. That collapses the per-layer cost from O(n^2) to O(n log n). The catch is honesty about the precondition: you must actually have monotone optima, and the divide-and-conquer optimization is wrong if you do not.
A close relative governs interval DPs. When the merge cost satisfies the quadrangle inequality — a kind of "concavity" saying wider intervals are not cheaper to split than narrower ones nested inside them — the optimal split points are monotone in both interval endpoints, and the Knuth-Yao speed-up shaves an entire interval DP from O(n^3) down to O(n^2). This is exactly the structure behind the optimal-binary-search-tree DP. The lesson across all three tools is one of recognition: ask whether your transition is a range sum (prefix sums), a min over lines (convex-hull or Li Chao), or a search with monotone optima (divide-and-conquer or Knuth-Yao). Recognizing the batchable shape is the whole skill; the implementation follows once you have named it.
Honest limits of the speed-up toolkit
None of these tricks change what the DP computes — they only compute it faster, and only when the transition has the right shape. The convex-hull trick needs the transition to be linear in the query variable; bend that line into a curve and the hull argument collapses. Divide-and-conquer and Knuth-Yao need genuinely monotone optima or the quadrangle inequality; assume monotonicity that does not hold and you get a fast wrong answer, the most dangerous kind. So the precondition is not paperwork — it is the correctness proof, and skipping it trades a slow correct program for a quick incorrect one.
And remember the opening caution: these are asymptotic wins. The constant factors of a balanced hull or a Li Chao tree are real, and for small n a flat O(n^2) double loop with sequential memory access can finish first. Reach for prefix sums freely — they are tiny and almost always help — but reach for the convex-hull trick, divide-and-conquer DP, or Knuth-Yao only when the input size or a profiler tells you the transition is truly the bottleneck. The art of fast DP is two-step: first get a correct DP with clear states and a clear transition, then, if and only if it is too slow, recognize which structural trick the transition was quietly offering all along.