What if you stopped caring about exactly ? Instead, add a penalty (lambda, a number you choose) for each segment you create. New goal: reduce (total cost + segment count). Solve this for different values.
When , you use as many segments as possible (no penalty). When is huge, you use few segments (they're expensive). Somewhere in between, you'll naturally use exactly segments. That's the trick.