Divide and Conquer DP Optimization — Filling One Row

dp[i][j] = min over k<j of ( dp[i-1][k] + C(k,j) ). Watch compute(l, r, optL, optR) resolve the middle column, then recurse with narrowed split windows.

step 0

DP rows (filling row i = 1 from row 0)

Scanning split points k for the current mid column.
Resolving column mid: try each split k in the window, keep the smallest k achieving the minimum — that is opt(mid).
split window [optL, optR] current mid column chosen opt(mid) resolved column
D&C cost checks: 0 naive would do (this row): 0

compute(l, r, optL, optR) call tree

Press Step to begin. We fill one DP row: pick the middle column, scan only its allowed split window, lock in opt(mid), then recurse left and right with windows narrowed by opt(mid).
Self-contained visualization. Cost C(k, j) = (prefixSum[j] - prefixSum[k])² (Monge), so opt(i, j) is non-decreasing in j. Row 0 is the base case (dp[0][0]=0, else ∞). Each compute call resolves its mid column by scanning [optL, min(optR, mid-1)], then recurses left with [optL, opt(mid)] and right with [opt(mid), optR]. See middle.md and professional.md for the O(n log n) proof.