Cheapest Way to Merge Piles
piles lists the sizes of piles of sand. In one step you merge any two piles into a single pile, and the step costs the size of the new pile (the sum of the two). You repeat until only one pile is left.
Return the smallest possible total cost of all the steps. The smallest total is unique, so no tie rule is needed. Return 0 when piles has fewer than two piles.
Example 1
piles [4,3,2,6]
returns 29
Merge 2 and 3 (cost 5), then 4 and 5 (cost 9), then 6 and 9 (cost 15): 29 in total.
Example 2
piles [1,2,3]
returns 9
Merge 1 and 2 (cost 3), then 3 and 3 (cost 6): 9. Merging 2 and 3 first would cost 5 + 6 = 11.
Constraints
0 <= len(piles) <= 1001 <= piles[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.