234 views

problem : You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Q.here i am not understanding why these problem is following fibonacci series??

### 1 comment

edited by
To reach $n^{th}$ stair either we were on $(n-1)^{th}$ stair or $(n-2)^{th}$ stair.

Therefore it is following fibonacci series

To count number of ways to reach $n^{th} stair$, it should be sum of number of ways to reach $(n-1)^{th}$ stair and number of ways to reach $(n-2)^{th}$ stair.

$f(n) = f(n-1) + f(n-2)$

1
177 views