title: Optimally cutting a stick at specified locations
body: <blockquote>
    <p>You have to cut a stick with length <code>l</code> into several pieces. Cuts have to be made at locations <code>c1, c2, c3, ..., cn</code>, where <code>ci</code> is an integer between <code>1</code> and <code>n-1</code> (inclusive). The cost of a cut is equal to the length of the stick on which it is made. What should be the order of the cuts to minimize the overall cost of the operation? </p>
    
    <p>For example, consider a stick of length <code>10</code> and cuts have to be made at locations <code>2, 4, 7</code>. You could cut the sticks in the order given. The first cut would cost <code>10</code>, since the stick is of length <code>10</code>. The second cut would cost <code>8</code>, since the remaining stick on which the cut is made is of length <code>10 - 2 = 8</code>. The last cut would cost <code>6</code>, since the length of the remaining stick is <code>10 - 4 = 6</code>. The total cost is <code>10 + 8 + 6 = 24</code>  </p>
    
    <p>But if we cut the stick in the order: <code>4, 2, 7</code>, we get the cost of <code>10 + 4 + 6 = 20</code> which is better for us. </p>
    
    <p>Design an algorithm to solve the problem. </p>
  </blockquote>
  
  <p>I'm pretty sure this is a DP problem. A tantalizing recurrence relation I could see was the fact that if we cut a stick, we get two smaller sticks. If we know the optimum solution for these two sticks, we can easily figure out the optimum solution for the larger stick. But this would be very inefficient.  </p>
  
  <p>If you have a recursive function <code>min_cost(stick_length, c_1, c_2, ..., c_n)</code> which returns the minimum cost of cutting a stick of length <code>stick_length</code> at <code>c_1, c_2, ..., c_n</code>, the recurrence relation would look something like this</p>
  
  <pre><code>min_cost(stick_length, c_1, c_2, ..., c_n) =
      stick_length 
      + minimum(min_cost(c_1, a_1, a_2, ..., a_i) 
      + min_cost (stick_length - c_1, 
                  a_(i+1), ..., a_(n-1)),
                  min_cost(c_2, a_1, a_2, ..., a_i) 
      + min_cost(stick_length - c_2, 
                 a_(i+1), ..., a_(n-1)), ... , 
                 min_cost(c_n, a_1, a_2, ..., a_i)
      + min_cost(stick_length - c_n,
                  a_(i+1), ..., a_(n-1)))`,
  </code></pre>
  
  <p>where <code>a_1, a_2, ..., a_n</code> is a permutation of the remaining places to be cut. We will have to pass all possible permutations to the recurrence function not just one as I have written. </p>
  
  <p>This is obviously impractical. How do I solve this? </p>