A row of sand piles has weights piles[0], piles[1], .... You repeatedly pick two neighbouring piles and merge them into one pile in the same spot; a merge costs the combined weight. You stop when one pile is left.
Implement min_merge_cost(piles: list[int]) -> int: the smallest possible total cost.
min_merge_cost([10, 20, 30]) # 90 (10+20) costs 30, then (30+30) costs 60
# merging 20+30 first would cost 50 + 60 = 110
min_merge_cost([4, 1, 1, 4]) # 18 (1+1)=2, then (4+2)=6, then (6+4)=10
A single pile needs no merges, so its cost is 0.
Constraints: 1 <= len(piles) <= 100, 1 <= piles[i] <= 1000. O(n³) is fine.
Show hint
the last merge of piles[l..r] joins some left part l..k with a right part k+1..r and costs sum(piles[l..r]) whatever k is, so cost[l][r] = sum(l..r) + min over k of (cost[l][k] + cost[k+1][r]); fill the table by increasing interval length.