Dynamic Programming

Question

Let A(n) denotes the number of n bit binary string which have no pair of consecutive 1’s. Then the time complexity of the effective algorithm which uses dynamic programming to compute A(n) will be ____

1. O(n)
2. O(2^n)
3. O(n^3)
4. O(nlogn) 

Here, the answer given is O(n);

I didn’t get this even after going through the solution. If any one can understand the bellow solution help me  get it , THANK YOU :)

Comments

See if this helps..

https://gateoverflow.in/39636/gate2016-1-2

 

---

Thank you so much, got it :)