Course contentsShow
← Computer Science
Lesson 959 of 2,87222. Dynamic ProgrammingFree lesson

Divide and Conquer Optimization

Apply when optimal split points are monotonic to reduce complexity from O(n³) to O(n² log n).

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:

  1. Solve the middle state first
  2. Use its optimal split point to constrain left and right halves
  3. 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.