Count ways to reach the n’th stair

[acha-bill]

There are N stairs. A person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time.

Write a function, that counts the number of ways the person can reach the top.

For example, in the image below, there are 4 steps(levels). The person starts at step 1.

As you can see, there are 3 ways to reach the 4th step by climbing either 1 or 2 steps at a time.

[iancarson]

We can solve this using the intuition behind Fibonacci. This means that ways(n) = ways(n- 1) + ways(n -2).

[priyangshusarkar77]

solve this problem by recursion and then convert it into a dynamic programming