I solved the problem using Bottom-UP method as shown in the “hint” video. But also as I was more interested to know if this problem can be solved by Top Down DP or not, I attempted this problem again using “Normal Recursion”(No memorisation), and as expected got TLE on two test cases. I am curious to know how my code of ordinary recursion can be modified to integrate the Top Down approach. I do think that Top Down approach can be only applied when we do the main work while back tracking which is not the case in my recursion code(no work in backtracking). Still, wanted to have some extra insights on this matter(whether and how my recursion code can be modified to implement Top-Down DP approach). Here is my code which includes both the Bottom-UP and the Normal recursion(where I wanted to apply Top Down DP ):
Count the number of Binary Strings Problem
hello @a_krisna22
see here str is redundant parameter ,
only selected and pos are varying parameter so we will use 2d array to store answer for all unique pairs( unique pair of selected and pos) at array[selected][pos].
and since selected can take value between 0 and 1 ,pos can take value between 0 n-1.
your dimension of array should be (2*N).
rest is just standard top down.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.