The Insight

What if you stopped caring about exactly $K$? Instead, add a penalty $\lambda$ (lambda, a number you choose) for each segment you create. New goal: reduce (total cost + $\lambda \times$ segment count). Solve this for different $\lambda$ values.

When $\lambda = 0$, you use as many segments as possible (no penalty). When $\lambda$ is huge, you use few segments (they're expensive). Somewhere in between, you'll naturally use exactly $K$ segments. That's the trick.