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) 有问题欢迎指证 感恩