Breaking a String - Problem Statement

A string of length $n$ with $m$ break points. Each break costs the current string length. Find minimum total cost. $dp[i][j]$ = min cost to break segment between break points $i$ and $j$.

Cost of one break = segment length. Transition: $dp[i][j] = \min_{k} (dp[i][k] + dp[k][j]) + (pos[j] - pos[i])$. The length adds to all splits. QI holds. Apply Knuth: $O(m^2)$ total. Without improvement, $O(m^3)$. This is one of the cleanest examples of Knuth improvement. The cost function satisfies the quadrangle inequality.