Merge Neighbouring Piles in Groups

Hard

Piles of sand stand in a row, and pile i holds piles[i] buckets. In one move you take exactly group **adjacent** piles and pour them into one; the move costs the total number of buckets in those piles. The new pile takes their place in the row. Return the minimum total cost to gather all the sand into a single pile, or -1 if that is impossible.

Example 1

piles=[4, 1, 2, 6], group=2 → 23

Merge 1 and 2 (cost 3), then 4 and 3 (cost 7), then 7 and 6 (cost 13). The total of 23 is the best possible.

Example 2

piles=[5, 5], group=3 → -1

There are only two piles but merges take three at a time, so one pile can never be formed.

Example 3

piles=[2, 7, 1, 3, 5], group=3 → 27

Constraints

1 ≤ len(piles) ≤ 30
1 ≤ piles[i] ≤ 100
2 ≤ group ≤ 30

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Prefix Sum

Similar problems

The Heaviest Reading Day Hard Cutting a Berry Cake Hard Ferry Runs From the Depot Hard Merge the Front Tiles Hard Coins From the Stacks Hard

Input

piles=[4, 1, 2, 6], group=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 219 tests on the server, hidden ones included.