title: Adding sum of frequencies whille solving Optimal Binary search tree
body: <p>I am referring to <a href="http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/" rel="nofollow noreferrer">THIS</a> problem and solution.</p>
  
  <p>Firstly, I did not get why sum of frequencies is added in the recursive equation.
  <img src="https://i.stack.imgur.com/SIrLP.jpg" alt="enter image description here">
  Can someone please help understand that with an example may be.</p>
  
  <p>In Author's word. </p>
  
  <blockquote>
    <p>We add sum of frequencies from i to j (see first term in the above
    formula), this is added because every search will go through root and
    one comparison will be done for every search. </p>
  </blockquote>
  
  <p>In code, sum of frequencies (purpose of which I do not understand) ... corresponds to fsum.</p>
  
  <pre><code>int optCost(int freq[], int i, int j)
  {
     // Base cases
     if (j &lt; i)      // If there are no elements in this subarray
       return 0;
     if (j == i)     // If there is one element in this subarray
       return freq[i];
  
     // Get sum of freq[i], freq[i+1], ... freq[j]
     int fsum = sum(freq, i, j);
  
     // Initialize minimum value
     int min = INT_MAX;
  
     // One by one consider all elements as root and recursively find cost
     // of the BST, compare the cost with min and update min if needed
     for (int r = i; r &lt;= j; ++r)
     {
         int cost = optCost(freq, i, r-1) + optCost(freq, r+1, j);
         if (cost &lt; min)
            min = cost;
     }
  
     // Return minimum value
     return min + fsum;
  }
  </code></pre>
  
  <p>Secondly, this solution will just return the optimal cost. Any suggestions regarding how to get the actual bst ?</p>