Don't you think it would give same answer for any value of k as S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i<=k<j. Ultimately all are getting sum up. For example S[i,j] = j - i +1 + min ( k-i+1 + j-(k+1) + ... ) which gives s[i,j] = j-i +1 + min ( j-i -1 + ... ). So it does not depend on the value of k.
I think the recurrence relation should be s[i,j] = ( j - i +1) + (j - k) + min ( s[i,k]+s[k+1,j]) for all i<=k<j, it also suits the example you gave of 20 char str gets divided at position 3 means 20 + (20 -3.) = 37. On Thu, Oct 17, 2013 at 3:51 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: > I have find out the minimum cost using the recurrence relation > > S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i<=k<j. > > But i could not find a way to print optimal cut sequence.Any pointers? > > > On 16 October 2013 23:13, atul anand <atul.87fri...@gmail.com> wrote: > >> 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. >> > > -- > 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. > -- navneet singh gaur -- 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.
