TLE again for 3rd time in row!

#1

I am always getting TLE !!
I have solved starting 2 problems of recursion - Tiling and Paranthesis. Both got TLE and I later used memorise technique in Tiling and proper recursion on Parenthesis generator. Now, I think I have used proper recursion but I am getting TLE. Whats the way out?? I think the time complexity of my code is O(3^n) using recursion. My code is here - https://ide.codingblocks.com/s/157698. Please tell me way out and also if my estimate of time complexity for above code is correct?

#2

I know I will get TLE because input size is 90 and my code grows exponential!

#3

But we need to use recursion na? Cos question toh recursion module m diya h

#4

I have solved the problem without using recursion. I used the pnc method which roughly took O(n^2) complexity.

#5

We will use bottom up DP and get this things done in linear time!
Just think from length 1…2…3…
You’ll find a pattern. It’s easy.
Think for it!!

#6

I don’t know DP at all. Vo toh bhot baad m padhayenge is course m. I think I should hold this problem then.

#7

Yeah right.
Hold it then. Once you complete DP section them come back to this problem :slight_smile:

#8

You may close the thread and mark your doubt resolved now .