A string of length with break points. Each break costs the current string length. Find minimum total cost. = min cost to break segment between break points and .
Cost of one break = segment length. Transition: . The length adds to all splits. QI holds. Apply Knuth: total. Without improvement, . This is one of the cleanest examples of Knuth improvement. The cost function satisfies the quadrangle inequality.