562. Merging k Piles at a Time

Piles of stones sit in a row. One move takes exactly k CONSECUTIVE piles and merges them into a single pile, at a cost equal to their total. Repeat until one pile remains.

Print the smallest total cost, or -1 if it cannot be done.

piles 3 2 4 1, k = 2 -> 20 piles 3 2 4 1, k = 3 -> -1 piles 1 2 3, k = 3 -> 6 one move merges everything

## When it is impossible

Each move turns k piles into 1, reducing the count by k - 1. Starting from n and ending at 1 needs n - 1 to be divisible by k - 1.

That is necessary and sufficient, and it must be checked FIRST, because the recurrence below quietly produces a number for impossible inputs if the feasibility is not tested.

3 2 4 1 with k = 3 answers -1: four piles cannot reduce to one in steps of two.

## The state, and the piece that problem 555 did not need

With k = 2 every range can always be merged into one pile, so dp[i][j] always means "merged into one". With general k a range can only reach one pile when its length is congruent to 1 modulo k - 1, and otherwise the best it can do is a few leftover piles.

So dp[i][j] means "the cheapest way to merge the range as far as it can go", and how far that is depends on the length.

## The recurrence

``` dp[i][j] = min over m in i, i+(k-1), i+2(k-1), ... of dp[i][m] + dp[m+1][j]

then, if (j - i) is divisible by (k - 1): dp[i][j] += sum of the range ```

The split index m steps by k - 1, not by 1. That is the whole difference from problem 555, and it encodes the fact that the left piece must itself reduce to exactly one pile before it can take part in a final merge.

Stepping by 1 gives splits that cannot be realised, and the answer comes out too small.

## The conditional final cost

The range total is added ONLY when the range can be reduced to a single pile, which is when (j - i) is divisible by k - 1. That addition is the cost of the last merge.

When the range cannot reach one pile, no final merge happens inside it and nothing is added; the leftover piles get merged later as part of a larger range.

Adding the total unconditionally charges for merges that never happen.

## Boundaries

A single pile answers 0 for any k, since nothing needs merging. 1 with k = 2 answers 0.

k = 2 reduces exactly to problem 555: 3 2 4 1 answers 20 there and here, and 6 4 4 6 answers 40 in both. Those shared answers are worth checking, because they confirm the general code specialises correctly.

## Cost

Time O(n^3 / k). Space O(n^2).

Constraints - `1 ≤ n ≤ 100` - `2 ≤ k ≤ 100` - `1 ≤ pile size ≤ 1000`