Merge adjacent stones
You are given an array of positive stone weights. Repeatedly you may merge two ADJACENT piles into one, paying a cost equal to the sum of the two merged piles; the merged pile's weight is that sum. Merge everything into a single pile and return the minimum total cost. Constraints: 1 <= length <= 1000, 1 <= each weight <= 1000. The O(n^3) interval DP can be sped up to O(n^2) with Knuth's optimization, but an O(n^3) reference is acceptable for the given bounds.
Implement
min_merge_cost(stones: list[int]) → intExamples
in
[[1,2,3,4]]out19What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 40 min
solution.py
InputExpectedGot
[[1,2,3,4]]19not run yetsample