string - 最小破弦成本的动态规划

Question

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.

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.

这道题来自《算法》chapter6 6.9.

既然这个问题没有答案，我就是这么想的。

定义OPT(i,j,n)作为断弦的最低成本，i对于起始索引，j对于 String 和 n 的结束索引我可以使用的剩余切割次数。

这是我得到的:

OPT(i,j,n) = min {OPT(i,k,w) + OPT(k+1,j,n-w) + j-i} for i<=k<j and 0<=w<=n

对不对？请帮忙，谢谢!

Answer 1

我觉得你的递归关系可以变得更好。这是我想出的，将 cost(i,j) 定义为将字符串从索引 i 切割到 j 的成本。然后，

cost(i,j) = min {length of substring + cost(i,k) + cost(k,j) where i < k < j}