Binary String (n to 1)

#1

Hello,

It seems like in this problem we need to traverse from 1 to n despite n to 1.

https://ide.codingblocks.com/s/233264 (1 to n)
https://ide.codingblocks.com/s/233256 (n to 1)

#2

Yes we need to travel 1 to n for bottom up dp,
one[1] = zero[1] = 1 where one[i] and zero[i] dones string of length i ending with 1 and 0 respectively.
relation follows: one[i+1] = zero[i]
zero[i+1] = one[i] + zero[i].

#3

Yeah using that relation i have solved the question from 1 to n .
Can it also be done for n to 1 in case of recursion or top down dp and how ? [this is the approach explained in hint video but i didn’t understood using that how we can implement the solution]

#4

Yes for top down dp, you can do this way:
// rough implementation
int ways(int len,int last_char){
if(len==0)
return 1;
if(last_char==1)
return ways(len-1,0); //this char can be 0 only
else
return ways(len-1,0)+ways(len-1,1);
}
do memoization also!

#5

I have tried the same solution using java but it’s not working.
Could you please suggest what I am missing.

#6

here ans = ways(n-1,0) + ways(n-1,1)
this is because once you set first letter as 1 and then as 0

#7

in case of lastdigit == 1 i am setting 0 and for lastdigit 0 i am adding 0 and 1 .

if(lastDigit == 1)
return countBinNum(num -1, 0);
else
return countBinNum(num-1, 0) + countBinNum(num-1, 1);

#8

Yes this is fine !
I was talking for final anwer!
you final answer is
cout<<ways(n-1,0) + ways(n-1,1);