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 wrote:
> I have f
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<=kwrote:
> 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
> But i could not find a way to print optimal cut
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 wrote:
> Question seems similar to matrix chain multiplication problemhere you
> need to find min cost..
> Recurrence for this could be the following , please validate it.
>
>
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 wrote:
