title: merge n coins with minimum cost to create one single coin
body: <p>From <a href="http://www.geeksforgeeks.org/amazon-interview-set-89/" rel="nofollow">http://www.geeksforgeeks.org/amazon-interview-set-89/</a></p>
  
  <blockquote>
    <p>We have n gold coins. We need to amalgamate all the n coins to create
    one single coin, we can merge two coins at once. The cost of merging
    two coins is equal to the value of those coins. How do we ensure that
    the cost of merging n coins in minimum.</p>
  
  <pre><code>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
  </code></pre>
    
    <p>If we had merged the coin array {5, 8, 4, 3, 9, 6} in different
    fashion:</p>
  
  <pre><code>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
  </code></pre>
    
    <p>As we can see that the cost is less in the first case. how to get the
    minimum cost of merging all the n coins??</p>
    
    <p>this is just an example, number of coins may of the range 10^9</p>
  </blockquote>