D&C Recursion - Walkthrough

Compute $dp[i]$ for $i \in [0, 7]$. Optimal splits are monotonic. Start with range $[0, 7]$. Compute $dp[3]$ (midpoint). Find $opt[3]$ by trying all valid splits. Say $opt[3] = 5$. Recurse on $[0, 2]$ with constraint $opt \in [0, 5]$. Recurse on $[4, 7]$ with constraint $opt \in [5, n]$.

Each level does $O(n)$ work total (all ranges at that level partition the search space). $O(\log n)$ levels gives $O(n \log n)$.