Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 63 ยท Dynamic Programming for Contests

DP Speedups

Speed up slow DP transitions in contests: sliding-window sums, monotone deques, the convex hull trick and divide and conquer optimization, each checked against a brute force.

A DP solution has two costs: the number of states and the work per transition. Most contest DPs that get Time Limit Exceeded have a perfectly good state space but a transition that loops over thousands of previous states. If dp[i] looks at the last k values, the total is n * k, and with n = k = 10^5 that is ten billion steps. The fix is rarely a new recurrence. It is a smarter way to answer the question "what is the best (or the sum of) these earlier values?".

This lesson covers four standard speedups, from simple to advanced: running window sums, monotone queues, the convex hull trick, and divide and conquer optimization. Each one needs a property of the transition, so we also learn how to recognize when it applies. Every technique is tested against its slow version, the habit from stress testing. You should already know the patterns in DP problem patterns and the prefix-sum idea from prefix sums and difference arrays.

flowchart TD
  A["Slow transition:<br/>dp[i] = best over many j"] --> B{"What is combined?"}
  B -->|"sum of a sliding range"| C["Running window sum"]
  B -->|"min or max of a sliding range"| D["Monotone deque"]
  B -->|"min of dp[j] + b[j]*a[i]"| E["Convex hull trick"]
  B -->|"min of dp[i-1][k] + cost(k,j)<br/>with monotone best k"| F["Divide and conquer"]

Choose the speedup from the shape of the transition.

Prefix sums and running windows

Suppose you want the number of ways to climb n stairs when each move goes up between 1 and k steps. The recurrence is dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k], a sum over a range that moves right by one each step. Summing the range every time costs k. But the range changes by one element on each side, so keep a running total: add the new value, subtract the value that falls out.

Python Ways to climb: slow sum against a running window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 3000 and k = 100 the slow loop does 295,050 additions and the fast one does 3,000. The same trick works for 2D DPs: if dp[i][j] sums a row segment of the previous row, keep a prefix-sum array of that row. This is also how counting DPs with "at most x of this item" run fast, because the allowed range of the previous layer is a contiguous block.

Under a modulus, subtraction can go negative in other languages. In Python % MOD always returns a value from 0 to MOD - 1, but remember the C++ fix (x - y + MOD) % MOD when you read other solutions. See modular arithmetic.

Monotone queue for window minimums

Now replace "sum" by "minimum". A frog starts on stone 0 and may jump up to k stones ahead. Landing on stone i costs cost[i]. The cheapest total cost to reach stone i is cost[i] + min(dp[i-k .. i-1]). A running total does not work for a minimum, because you cannot "subtract" a minimum when it leaves the window.

A monotone deque solves it. Keep indices in a queue whose dp values are increasing from front to back. The front is always the minimum of the window. Three rules maintain it:

  1. Before using the front, drop it if its index is older than i - k.
  2. After computing dp[i], pop from the back every index whose dp is greater than or equal to dp[i], because they are older and worse, so they can never be the best again.
  3. Push i at the back.

Each index is pushed and popped once, so the whole DP is O(n). This is the same structure that finds sliding-window maximums in monotonic stacks, heaps and deques.

Python Frog jumps with a monotone deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same idea handles "maximum" with the comparison flipped, and it also speeds up DPs of the form dp[i] = min over j of (dp[j] + f(i)) where f(i) does not depend on j.

The convex hull trick

Now consider transitions where the quantity depends on both i and j through a product:

dp[i] = min over j < i of ( dp[j] + b[j] * a[i] )

For a fixed j, the expression b[j] * x + dp[j] is a line in the variable x = a[i], with slope b[j] and intercept dp[j]. The transition asks for the lowest line at the point x = a[i]. If you keep only the lines that are lowest somewhere (the lower envelope, a convex shape), each query becomes a lookup.

Many problems hide this form behind a square. Take "Frog with a tax": stones at increasing heights h, a jump from j to i costs (h[i] - h[j])^2 + C. Expand the square:

dp[i] = h[i]^2 + C + min over j of ( dp[j] + h[j]^2 - 2*h[j]*h[i] )

Line j has slope -2*h[j] and intercept dp[j] + h[j]^2; the query point is h[i]. Because h increases, new lines have smaller and smaller slopes, and queries move to the right. That is the friendliest case: lines arrive sorted by slope, queries come in increasing order, so a stack plus a moving pointer gives O(n) overall.

flowchart LR
  L["New line arrives<br/>(smallest slope so far)"] --> T{"Does the last line<br/>stay on the envelope?"}
  T -->|"no"| P["Pop it and test again"]
  P --> T
  T -->|"yes"| A["Append the new line"]
  A --> Q["Query at x:<br/>advance pointer while next line is lower"]

Adding a line removes the lines it makes useless; queries only move the pointer forward.

The test "does the middle line stay on the envelope" compares intersection points. To avoid fractions, cross-multiply. All numbers stay integers, which is exact in Python and a reason to prefer integers over floating point.

Python Convex hull trick against the O(n^2) DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When slopes or queries are not sorted, use a Li Chao tree (a segment tree over the x-axis that stores one line per node) or binary search on the hull. When the problem is a maximum instead of a minimum, negate the values. Always remember the pattern, not the code: spot the product b[j] * a[i], and the transition becomes a line query.

Divide and conquer optimization

A third family splits a sequence into k groups. The state is dp[g][j] = best cost for the first j items in g groups, and the transition is

dp[g][j] = min over m < j of ( dp[g-1][m] + cost(m, j) )

Done directly it takes O(k * n^2). Let opt(j) be the split point m that wins for j. If opt(j) never decreases as j grows (a property true for many "convex-like" cost functions, such as the square of a segment sum with non-negative values), you can compute a whole layer by recursion:

  1. Compute the middle j by scanning only m in [optLow, optHigh], and remember its best m*.
  2. Recurse on the left half with m limited to [optLow, m*] and on the right half with [m*, optHigh].

Each recursion level scans about n split points in total, and there are log n levels, so a layer costs O(n log n) and the DP O(k * n log n).

Python Split into k groups: divide and conquer optimization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The monotone-optimum property is a claim you must justify, not assume. A random stress test like the one above is a quick sanity check, but a test that passes on small values does not prove the property. In contests, solvers rely on known cost shapes, or on the editorial, and then confirm with a brute force.

Choosing between them

Transition Technique Time
Sum over a sliding range of dp Running window sum / prefix sums O(n)
Min or max over a sliding range Monotone deque O(n)
min(dp[j] + b[j] * a[i]) Convex hull trick (Li Chao if unsorted) O(n) to O(n log n)
min(dp[g-1][m] + cost(m, j)), monotone opt Divide and conquer O(k n log n)

Before reaching for any of these, check that the slow solution is actually the bottleneck and that a simpler reformulation does not exist, as discussed in estimating time and memory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A DP computes dp[i] as the sum of dp[i-k] through dp[i-1]. What is the fastest simple way to speed it up?

    A sum over a sliding range changes by one element at each end per step, so adding the new value and removing the old one keeps it up to date in O(1).
  2. 2. In the monotone deque for window minimums, why can you pop from the back every index whose dp value is greater than or equal to the new one?

    An older entry leaves the window first, so if its value is not smaller than the new entry it can never be the answer again.
  3. 3. Which transition has the shape needed by the convex hull trick?

    For a fixed j, dp[j] + b[j] * x is a line in x. The transition asks for the lowest line at x = a[i].
  4. 4. What property lets divide and conquer optimization work?

    If the best split opt(j) is monotone, the left half of a layer can only use split points up to opt(mid) and the right half only from opt(mid) on.
  5. 5. Why does the convex hull code compare lines with cross-multiplication instead of division?

    Intersection points are fractions. Multiplying both sides by the positive denominators gives the same comparison with exact integers.

Summary

  • Slow DP transitions are usually fixed by answering the range question faster, not by changing the state.
  • A sum over a sliding range needs only a running total; a min or max needs a monotone deque.
  • The convex hull trick applies to min(dp[j] + b[j] * a[i]), where each j is a line queried at a[i].
  • Divide and conquer optimization computes a DP layer in O(n log n) when the best split point is monotone.
  • Each speedup depends on a property of the transition, so verify against a brute force before trusting it.

Next: String Algorithms in Contests