[問題] 數值合併
版上強者很多, 所以我又來問問題了
有一系列的數字, 每次挑兩個相鄰的數字合併
合併的數字按照原來順序插入序列之中, 合併的代價為 s , s 為兩個數字的和
經過一連串的合併之後, 整個序列會只剩下一個值, 而總合併代價為 S
問怎樣的合併動作, 總合併代價會是最小
範例一:
3 4 5 (3,4) 合併 代價 7
7 5 (7,5) 合併 代價 12
12 總代價 19
範例二:
5 3 4 5 (5,3) 合併 代價 8
8 4 5 (4,5) 合併 代價 9
8 9 (8,9) 合併 代價 17
17 總代價 34
5 3 4 5 (3,4) 合併 代價 7
5 7 5 (5,7) 合併 代價 12
12 5 (12,5) 合併 代價 17
17 總代價 36
可見greedy algorithm並非最佳解
用Dynamic programming的話, 存在一個 O(n^3)的演算法
不過有一個 O(nlogn)的演算法, 卻不得其門而入
有誰可以提示一下, 感激不盡
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.220.140
推
07/08 20:56, , 1F
07/08 20:56, 1F
推
07/08 21:02, , 2F
07/08 21:02, 2F
推
07/08 21:04, , 3F
07/08 21:04, 3F
討論串 (同標題文章)