The Problem

Here's the challenge: find the minimum cost (total penalty from all segments) to partition an array into exactly $K$ segments, where each segment has a cost (for example, the square of its element sum) and the total cost is the sum of all segment costs.

Without the "exactly $K$" constraint, simple DP suffices: $dp[i]$ = best cost to partition positions $1$ to $i$.

But "exactly $K$" forces you to track count: $dp[i][k]$ = best cost using exactly $k$ segments ending at position $i$. With $n = 50{,}000$ and $K = 5{,}000$, that's $250$ million states. The extra dimension comes from the constraint. What If could remove the constraint and get the right answer?