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| &, |C| = 1 \\
|s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' c\}) \end{align}\right] &, \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.

StackExchange Computer Science Q#1822, answer score: 11