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.
