solution

Có $n$ đống đá xếp thành hàng, đống thứ $i$ có $a_i$ viên. Mỗi bước, ta gộp hai đống liền kề thành một đống mới; chi phí của bước đó bằng tổng số viên của hai đống. Quá trình tiếp tục đến khi còn một đống.

Hãy tìm tổng chi phí nhỏ nhất để gộp tất cả về một đống. Vì hàm chi phí thoả điều kiện tứ giác (quadrangle inequality), có thể dùng tối ưu Knuth đưa độ phức tạp về $O(n^2)$.

Ví dụ: $a = [1, 2, 3]$: gộp $1{+}2=3$ (chi phí $3$) rồi $3{+}3=6$ (chi phí $6$), tổng $9$. Đây là phương án tối ưu.