DP(Count Number of Binary Strings)

#1

how to approach this problem by Top Down DP. I am only able to see it as sequence of Fibonacci numbers.

#2

yes your approach is correct
for a given n the number of strings will be (n+2)th fibbonacci numbers
for the dp approach
Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:

a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1]

The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].