Dynamic Programming • Optimization

Divide and Conquer Optimization

Optimize DP from O(K * N^2) to O(K * N log N) when the optimal split point `opt(i, j)` satisfies monotonicity: `opt(i, j) <= opt(i, j+1)`.

Try Interactive Simulator

Overview

Used for problems where we partition an array into K segments minimizing cost. Normal DP takes O(N^2) per segment. We can reduce this if the cost function satisfies the quadrilateral inequality.

Monotonicity

If the optimal split point `opt(i, j)` for segment length `j` moves to the right as `j` increases, we know that `opt(i, j-1) <= opt(i, j) <= opt(i, j+1)`.

Divide and Conquer

Instead of iterating `j` sequentially, we compute it for `mid`. The found `opt(mid)` restricts the search space for the left half `[left, mid-1]` to `[optLeft, optMid]` and the right half to `[optMid, optRight]`.

Key Insight

Because the search space is halved at each recursion depth, the total work per level is O(N). The recursion depth is O(log N), giving O(N log N) per row.

Array Indices (1 to 6)

1

2

3

4

5

6

Search Range: [1, 6]Opt Bounds: [1, 6]

Code Tracker

:::

1function compute(i, left, right, optLeft, optRight) {

2 if (left > right) return;

3 let mid = Math.floor((left + right) / 2);

4 let best = Infinity, optMid = -1;

5 for (let k = optLeft; k <= Math.min(mid, optRight); k++) {

6 let cost = dp[i-1][k-1] + costFunc(k, mid);

7 if (cost < best) { best = cost; optMid = k; }

8 }

9 dp[i][mid] = best;

10 compute(i, left, mid - 1, optLeft, optMid);

11 compute(i, mid + 1, right, optMid, optRight);

12}

Divide And Conquer Optimization

Divide And Conquer Optimization

Divide and Conquer Optimization

Overview

Monotonicity

Divide and Conquer

Key Insight

Divide and Conquer Optimization

Overview

Monotonicity

Divide and Conquer

Key Insight