Why D&C Is O(n log n)

The recursion depth is $O(\log n)$ because you halve the state range each time. At each depth, the search ranges $[optL, optR]$ across all calls are nearly disjoint. When you find $opt[mid] = k$, the left child gets range $[optL, k]$ and the right child gets $[k, optR]$. These don't overlap except at $k$.

So all calls at the same depth search a total of $O(n)$ values. With $O(\log n)$ depths, total work is $O(n \log n)$. For layered DP with $g$ layers, you run D&C once per layer: $O(g \cdot n \log n)$ total.