# Help in SPOJ ANARCO9A solution using DP.

[ANARCO9A][1]
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 :)

[1]: http://www.spoj.com/problems/ANARC09A/
[2]: http://abitofcs.blogspot.in/2014/10/a-bit-of-string-balancing-spoj-anarc09a.html
[3]: http://ideone.com/V5mX51``````

hey here is a <a href “http://ideone.com/tEpmdJ” > link of your code where slight modification made compare both code and find error. this is your homework

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....... ?

[1]: http://ideone.com/7bjOr8``````

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

got link to code here it is if any one comes to this post in future -> [http://ideone.com/tEpmdJ