dynamic programming exercise on cutting strings I have been working on the following problem from this book.


  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$.


I need a dynamic programming algorithm that given $m$ cuts, finds the minimum cost of cutting a string into $m +1$ pieces.
The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.

In formula:

$\qquad \displaystyle \operatorname{mino}(s, C) = 
  \begin{cases} 
    |s| &amp;, |C| = 1 \\
    |s| + \min_{c \in C} \left[ \begin{align}&amp;\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' &lt; c\})\ \\ +\ &amp;\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' &gt; c\}) \end{align}\right] &amp;, \text{ else}
  \end{cases}$

Note that applying memoisation to this recursion actually saves work as switching the order of any successively applied pair of cuts results in the same three subproblems being solved.