What Is D&C Optimization?

You want to compute $dp[1], dp[2], \ldots, dp[n]$ where Base case: $dp[0] = 0$. For $i \geq 1$: $dp[i] = \min_{j < i}(dp[j] + cost(j,i))$. Naively, each takes $O(n)$ time.

D&C improvement computes the middle element first: $dp[mid]$. Finding $opt[mid]$ takes $O(n)$ time.

But now you know: for all $i < mid$, search only $j \leq opt[mid]$. For all $i > mid$, search only $j \geq opt[mid]$. Recurse on both halves.

Each level of recursion does $O(n)$ total work. Picture a binary tree: at the root Compute $dp[n/2]$, its children compute $dp[n/4]$ and $dp[3n/4]$. Each level handles $O(n)$ work total across all nodes. With $O(\log n)$ levels, total is $O(n \log n)$.