Breaking a String - Implementation

Add 0 and $n$ as dummy break points. Now we have $m+2$ points, and we need to fully break the string. Base case: $dp[i][i+1] = 0$ (no break needed between adjacent points). Fill by increasing gap: gap = 2, 3, ..., $m+1$. For each $(i, j)$ with gap $j - i$, search $k \in [opt[i][j-1], opt[i+1][j]]$. Time: $O(m^2)$, Space: $O(m^2)$. Track $opt[i][j]$ alongside $dp[i][j]$. Add sentinel break points at 0 and n to handle boundaries cleanly. The actual breaks are between sentinels.

Time complexity: $O(n^2)$.

Space complexity: $O(n^2)$.