Divide and Conquer Optimization
You'll learn how to speed up certain DP recurrences from O(n³) to O(n² log n) by exploiting monotonicity in optimal split points.
The Core Idea
Imagine you're solving a DP problem where each state depends on splitting an interval at the "best" position. Normally, you'd try every possible split point for every state—expensive!
But here's the magic: if the optimal split point never moves backward as you progress, you can use divide-and-conquer to find all split points much faster.
How It Works
Suppose your DP recurrence looks like:
dp[i] = min(dp[j] + cost(j, i)) for all j < i
Monotonicity condition: If opt[i] is the best j for state i, then:
opt[i] ≤ opt[i+1] ≤ opt[i+2] ...
When this holds, instead of checking all j for each i, you:
- Solve the middle state first
- Use its optimal split point to constrain left and right halves
- Recursively solve those halves
Why it's faster: You compute each state only once during the divide-and-conquer recursion, and each split computation touches only a subset of states. The logarithmic recursion depth reduces the total work from O(n³) to O(n² log n).
When to Use It
- Matrix chain multiplication variants
- Problems where partitioning ranges and the best split "slides forward"
- Already using tabulation but bottlenecked by the innermost loop
Think of it like binary search applied to DP: you halve the problem space at each step instead of scanning linearly.
Key Takeaway: When optimal split points are monotonic (never decrease), divide-and-conquer optimization dramatically reduces DP complexity by recursively narrowing the search space instead of brute-forcing every split.