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) 有問題歡迎指證 感恩