All problems

Pile Merging

Hard · dynamic programming

Some piles of stones sit in a row. The list piles gives the number of stones in each pile, from left to right.

In one move you pick two piles that are next to each other and merge them into a single pile. The new pile holds all the stones of the two old ones, and the move costs as many stones as the new pile holds. The new pile takes the place of the two old piles, so the row gets one pile shorter.

Keep merging until only one pile is left. Return the smallest possible total cost over all the moves. If there is only one pile to begin with, no move is needed and the answer is 0.

You may merge in any order, as long as every move joins two neighbouring piles.

Examples

Example 1

Input: piles = [4, 1, 2]

Output: 10

Merge the piles 1 and 2 first (cost 3), giving [4, 3]. Then merge those (cost 7). The total is 10. Starting with 4 and 1 instead costs 5 + 7 = 12.

Example 2

Input: piles = [5]

Output: 0

There is already one pile, so no move is made.

Example 3

Input: piles = [3, 3, 3, 3]

Output: 24

Merge the left pair (6) and the right pair (6), then the two new piles (12). The total is 6 + 6 + 12 = 24.

Constraints