A potter has a row of clay lumps with masses lumps. She repeatedly presses two neighbouring lumps into one; this costs the combined mass of the two lumps, and the new lump takes their place in the row. Return the smallest total cost of pressing the whole row into a single lump.
Examples
Input: lumps = [4, 1, 3]
Output: 12
Explanation: press 1 and 3 (cost 4), then 4 and 4 (cost 8).
Input: lumps = [7]
Output: 0
Constraints
0 <= len(lumps) <= 1001 <= lumps[i] <= 1000- The number of merge orders grows faster than exponentially; aim for O(n**3).
Goals
- Recognise that the final merge splits the row into two independent halves
- Use prefix sums to get interval weights in O(1)