以最低成本合并n个硬币以创建一个单一硬币

来自http://www.geeksforgeeks.org/amazon-interview-set-89/

我们有n个金币.我们需要将所有n个硬币合并为一个硬币,我们可以同时合并两个硬币.合并两个硬币的成本等于这些硬币的价值.我们如何确保合并n个硬币的成本最低.

Ex: 5 ,8 , 4, 3, 9, 6
We will merge 3 and 4, cost=7 {Remaining coins: 5,8,9, 6,7}
Then we merge 5 and 6, cost=11 { Remaining coins: 11,8,9,7}
Then we merge 7 and 8, cost=15 { Remaining coins: 11,15,9}
Then we merge 9 and 11, cost=20 { Remaining coins: 20,15}
Then we merge 20 and 15, cost=35 { Remaining coins: 35}
Total cost: 7+11+15+20+35 = 88

如果我们以不同的方式合并了硬币阵列{5,8,4,3,9,6}:

Merging 5 and 8, cost=13 {Remaining coins: 13, 4, 3, 9, 6}
Merging 13 and 4, cost=17 {Remaining coins: 17, 3, 9, 6}
Merging 17 and 3, cost=20 {Remaining coins: 20, 9, 6}
Merging 20 and 9, cost=29 {Remaining coins: 29, 6}
Merging 29 and 6, cost=35 {Remaining coins: 35}
Total cost: 114

我们可以看到,在第一种情况下成本较低.如何获得合并所有n个硬币的最低成本？

这只是一个例子,硬币的数量可以是10 ^ 9的范围

Patrick87.. 9

我没有考虑过这个问题,但是从头脑中看,贪婪的方法很可能会起作用:对硬币进行排序并始终先合并最小的硬币.这背后的直觉是你想要尽可能不频繁地"合并"最昂贵的硬币.

如果你有一枚硬币,你就完成了.如果你有两个硬币,你只有一个选择.考虑具有三个硬币的情况:A

A + B, (A + B) + C => 2A + 2B + C
A + C, (A + C) + B => 2A + 2C + B
B + C, (B + C) + A => 2B + 2C + A