The D&C Recursion

Define $solve(l, r, optL, optR)$: compute $dp[l..r]$ knowing optimal splits are in $[optL, optR]$.

$1.$ Base case: if $l > r$, return.

$2.$ Compute $mid = (l + r) / 2$.

$3.$ Find $dp[mid]$ by trying all $j \in [optL, \min(optR, mid-1)]$. Track which $j$ was best as $opt[mid]$.

$4.$ Recurse: $solve(l, mid-1, optL, opt[mid])$ and $solve(mid+1, r, opt[mid], optR)$.