title: dynamic programming for minimum cost of breaking the string
body: <blockquote>
  <p>A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30.</p>
  <p>Give a dynamic programming algorithm that, given the locations of m cuts in a string of length n, finds the minimum cost of breaking the string into m + 1 pieces.</p>
  </blockquote>
  <p>This problem is from &quot;Algorithms&quot; chapter6 6.9.</p>
  <p>Since there is no answer for this problem, This is what I thought.</p>
  <p>Define <code>OPT(i,j,n)</code> as the minimum cost of breaking the string, <code>i</code> for start index, <code>j</code> for end index of String and <code>n</code> for the remaining number of cut I can use.</p>
  <p>Here is what I get:</p>
  <p><code>OPT(i,j,n) = min {OPT(i,k,w) + OPT(k+1,j,n-w) + j-i} for i&lt;=k&lt;j and 0&lt;=w&lt;=n</code></p>
  <p>Is it right or not? Please help, thx!</p>