Question seems similar to matrix chain multiplication problem....here you need to find min cost.. Recurrence for this could be the following , please validate it.
DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i < k < j && i < j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: > I was not able to figure out the solution to the problem in CLRS 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 (say size of this set is k), 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. So the task is to > find out which sequence gives the minimum cost and what is that sequence > out of k! possible sequences. > > I have seen the solutions in stack overflow using divide and conquer, but > i would like to know how to solve this problem using DP. Someother > solutions in the web shows it can be solved in O(n^3) or O(n^2) but no > where i have seen the sub problem(Optimal substructure) defined. > > I was not able to identify sub problems and make a recurrence relation out > of it.Can someone please throw light on this? I just want to develop > approach to solve the DP problems. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
