https://i.imgur.com/3qPTUj3.jpg
https://i.imgur.com/EzJ47yM.jpg
问这题，前情提要答案是 D
而原题答案 X = 91
(4 + 4) + 8 + (5 + 4) + (3 + 5)
= (8 + 8) + (9 + 8) = (16 + 17)
→ 8 + 9 + 8 + 16 + 17 +33 = 91
我是想问算法实作的部分，
看之前上讨论只说可以用 matrix chain 类似方式去求解，
而 matrix chain 最快可在 O(n lg n )下实作
该篇算法
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf
以下是我的想法 :
Find_Small_Intermediate_Sum(int *list, int list_size)
Sequential search list, determine the total size is odd or even
if(list_size % 2 == 0){
Divide the list into group, which group size is 2
Calculate the sum for the each group, put it into the list
Find_Small_Intermediate(list, list_size / 2)
}else{
list \ the biggest one // Don't calculate the biggest one
Divide the list into group, which group size is 2
Calculate the sum for the each group, put it into the list
Find_Small_Intermediate(list, list_size / 2)
}
# 算法步骤
1. Split the list // O(log n)
2. 判断总数为何 若为基数 先去除最大项, 偶数不变 // O(n)
3. 接下来依剩下储存值与相临数值相加之后 merge // O(n)
有问题欢迎指证 感恩