Here's the challenge: find the minimum cost (total penalty from all segments) to partition an array into exactly 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 " constraint, simple DP suffices: = best cost to partition positions to .
But "exactly " forces you to track count: = best cost using exactly segments ending at position . With and , that's million states. The extra dimension comes from the constraint. What If could remove the constraint and get the right answer?