Given value of n the length of sequence we have to tell total number of valid parenthesis sequences.
eg
n=2 ans=1 {}
n=3 ans=0 since n is odd not possible to form any one
Note -> he explicitly mentioned he want both memo version and bottom up and these two will be considered as two ques for my phone interview.
Initially i tried with bottom up but i couldn't
Interviewer also gave hint and told that there are multiple approaches using bottom up dp .
And he also mentioned about catalan numbers.
But i didn't hear of catalan numbers.

In the end when 15 min were remaining i tried with memo version
by maintaing open and close two variables .But i again got stuck in memo approach.

can any help me how can i solve using topdown and bottom up?