Can you tell me , what are the overlapping sub-problems in this question . Because we need to apply DP only when there are overlapping sub-problems , but I am unable to find those overlapping sub-problems in this question.
Doubt regarding count number of binary string problem
@Lalit2142 Hi buddy, sometimes you have to think out of the box in dp problems. I will told you how:-
say n = 5
So one possible string is 10100
another 10101
did you see that 101 part common, there you get that overlapping subproblem part.
so basically that string of length 3 is overlapping.
Okay another thing is that you can try to figure out a pattern in it.
n = 1, count = 2 = fib(3)
n = 2, count = 3 = fib(4)
n = 3, count = 5 = fib(5)
n = 4, count = 8 = fib(6)
n = 5, count = 13 = fib(7)
So I have given you two approaches, now you can try whatever you want.
Also bro if your query is clear. do remember to close the doubt by marking it resolved and rate full else feel free to ask buddy.
Happy coding!