Chapter 9: DP Optimization Techniques

You have learned to derive recurrences and fill DP tables. For many problems, the straightforward implementation is O(n²) or O(n³) — perfectly fine for interview-sized inputs. But in competitive programming and on large datasets, that complexity TLEs (Time Limit Exceeded). This chapter covers the advanced optimizations that turn intractable recurrences into efficient algorithms.

The key skill is recognition: before reaching for an optimization, confirm your naive DP is correct. Then ask whether the cost function or recurrence structure has special properties — monotonicity, quadrangle inequality, linear separability — that unlock a faster method.

Monotone Queue Optimization

When it applies: Your recurrence scans a sliding window of previous states:

dp[i] = min/max over j in [i-k, i-1] of (dp[j] + cost(j, i))

Equivalently: each dp[i] depends only on the best value in a window of size k.

The naive approach tries every j in the window for each i — O(n·k). The monotone queue (deque) optimization maintains a deque of candidate indices in decreasing (for max) or increasing (for min) order of their values. When advancing i:

1. Pop from front — remove indices that fell out of the window (index ≤ i − k).
2. Pop from back — remove indices whose values can never be optimal because a newer, better candidate exists.
3. Push i — add the current index.
4. The front of the deque always holds the optimal j for the current window.

Why it works: If nums[j₁] ≤ nums[j₂] and j₁ < j₂, then j₁ is dominated — it is smallerand it expires from the window sooner. We never need to keep dominated candidates. Each index is pushed and popped at most once, giving amortized O(1) per step and O(n) total.

Example: Sliding Window Maximum

Given an array and window size k, return the maximum in each sliding window. This is the canonical monotone queue problem — not always framed as DP, but the recurrence is identical:

dp[i] = max(nums[j]) for j in [i-k+1, i]

Each window maximum depends only on the previous k elements.

Divide & Conquer Optimization

When it applies: You have a 2D DP where each cell depends on a range of split points:

dp[i][j] = min over k in [i, j-1] of (dp[i][k] + dp[k+1][j] + w(i, j, k))

If the optimal split point opt(i, j) is monotone — that is, opt(i, j) ≤ opt(i, j+1) and opt(i, j) ≤ opt(i+1, j) — then you can compute an entire row of the DP table using divide and conquer in O(m·log n) instead of O(m·n).

Condition: The cost function must satisfy the quadrangle inequality (also called Monge property or concavity):

w(i, j, k) + w(i', j', k') ≤ w(i, j, k') + w(i', j', k)
for i ≤ i' ≤ k ≤ k' ≤ j ≤ j'

Intuitively: merging earlier is never worse than merging later when the intervals overlap in a certain way. Common in partition DP and some knapsack variants.

How it works: To fill row i for columns [l, r], compute the midpoint m = ⌊(l+r)/2⌋ first. Search for opt(i, m) only in a narrowed range [optLo, optHi]. Then recursively fill [l, m−1] with [optLo, opt(i,m)] and [m+1, r] with [opt(i,m), optHi]. Each row costs O(m·log n), total O(n·m·log n).

Knuth's Optimization

When it applies: Interval DP of the form:

dp[i][j] = min over k in [i, j-1] of (dp[i][k] + dp[k+1][j] + cost(i, j))

If the cost function satisfies the quadrangle inequality and the monotonicity of optimal splits:

opt(i, j-1) ≤ opt(i, j) ≤ opt(i+1, j)

then instead of trying all k from i to j−1, you only need to search from opt(i, j−1) to opt(i+1, j). The search range for each cell is tiny — often O(1) amortized per cell.

Time: O(n²) instead of O(n³). This is a special case of interval DP where the cost depends only on the endpoints (not on k), such as matrix chain multiplication with certain cost structures, optimal BST, and some merge-stone variants.

Convex Hull Trick (CHT)

When it applies: Your recurrence has the form:

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

Each previous state j defines a linear function f_j(x) = b[j]·x + dp[j]. You want the minimum of these lines evaluated at x = a[i]. The set of lines forms a convex hull; only lines on the lower hull can be optimal.

How it works: Maintain a deque of lines forming the lower convex hull. When adding a new line, pop from the back while the second-to-last line is dominated. When querying at x = a[i], pop from the front while the second line gives a better (lower) value.

• If slopes b[j] are added in sorted order: O(n) total (each line added and removed once).
• If slopes are unsorted: sort first or use a Li Chao segment tree — O(n log n).

Classic applications: tasks scheduling with linear cost, divide array with linear penalty, and some resource allocation problems.

Summary: Which Optimization When?

What's Next

Optimization is the final layer of mastery. The next chapter shifts from building solutions to recognizing which pattern applies — the skill that lets you deploy everything you have learned under time pressure. Keep this summary table handy when a naive DP is correct but too slow.