Question

好心的高手帮解一道C++递归题目

题目：在一个桌子上顺序摆放有4个砝码，已知它们的质量分别为4，4，5，9克。现在要将砝码按次序地合并成一堆，规定每次只能选相邻的2堆砝码合并成新的一堆，并将新的一堆砝码的总质量记为该次合并的得分。编程求出将这4堆砝码合并成一堆的最大得分。
如：[ ( 4 + 4 ) + 5 ] + 9 = 43 分
第一次：8 第二次：13 第三次：22 8+13+22=43
（没多少分了，不好意思）

Answer 1

（4+4）+（4+4+5）+（4+4+5+9）=43
分别定义数组a[0]=4;a[1]=4;a[2]=5;a[3]=9,n=4
sum=(a[0]+a[1])*(n-1)+a[2]*(n-2)+a[3]*(n-3);
从这个表达式可以看出，从第一项到最后一项的系数递减
所以大数放到前面的值是最大的。

Answer 2

我感觉按重量从高到低依次合并就是最大得分。