In a string of length

n$,$ the computational cost of splitting between index i and i $+1($indexed from $1)$ is n for

any index i$.$ Call such an operation a split at i$.$ If you want to split your string into multiple

pieces, this means it matters what order you perform the splits in$.$ Formally:

Input: A string s $=$ s$1...$ sn and split locations $0=$ l$(0)<$ l$(1)<...<$ l$($k$)<$ l$($k $+1)=$ n$.$

$[$Note: We are defining l$(0)$ and l$($k $+1)$ for your convenience later.$]$

Output: The smallest cost of splitting at l$(1),...,$ l$($k$),$ over all orderings of the splits.

Example: s $=$ axdf jkl$.$ l$(1)=1,$ l$(2)=4.$ This means we need to split the string s into

substrings a$,$ xdf$,$ and jkl$.$ If we start with the split at $1,$ we incur a computational cost of $7$

for the first split, plus $6$ for the second, for $13$ total. If we split at $4$ then $1$ instead, we incur

$7+4=11,$ which is preferable.

Here$$s a helpful subproblem for this problem. Let OPT$($i$,$ j$)$ be the minimum cost of splitting

the substring sl$($i$)+1...$ sl$($j$)$ at each of l$($i $+1),...,$ l$($j $1).$ Give a DP algorithm with detailed runtime.