Hi Raja,
You can store positions cuts in a separate 2d array ( say
C[i][j] ) similar to S[i,j] to store optimal cut position for string
running from index i to j and use recursion to print cut positions.
-Thanks
Bujji
On Thu, Oct 17, 2013 at 3:21 AM, kumar raja
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=kj. 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
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=kj.
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
Question seems similar to matrix chain multiplication problemhere 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
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