Help in SPOJ ANARCO9A solution using DP.

I am trying to solve it using following recursion ->

Let S(k, open) be the number of min operations to balance the string
with |open| open brackets by the time we start at k.
Let current bracket be cur. We have several cases:

  1. open is 0, and cur = ‘}’, then we have to flip.
    S(k, open) = 1 + S(k+1, open+1)
    open is 0 and cur = ‘{’, then we cannot flip.
    S(k, open) = S(k+1, open+1)
  2. open > 0 and cur = ‘}’. We can use cur to close an open bracket, or
    flip it to add new open brackets.
    S(k, open) = min( S(k+1, open-1), 1 + S(k+1, open+1) )
  3. open > 0 and cur = ‘{’, then we have
    S(k, open) = min( S(k+1, open+1), 1 + S(k+1, open-1) )

SOURCE : [[source][2]]. but It doesn’t works for cases like -> ‘{{{}’ or ‘{{{}{{{}’

My Code ->

[3] can you help in this ?

Thanks :)


hey here is a <a href “” > link of your code where slight modification made compare both code and find error. this is your homework :stuck_out_tongue: :slight_smile:

If didn’t get ask.

1 Like

I tried to implement it with DP

[1]. But still it gives TLE, I don't know why it's getting TLE even when I used memoization. Any small hint ?? @paras885  

any help....... ?


bro plz check ur link it’s URL of this post(recursive :P).

got link to code :smiley: here it is if any one comes to this post in future -> [