### 70. Climbing Stairs

Problem:

You are climbing a stair case. It takes n steps to reach to the top.

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

Classical Dynamic Programming Problem.

- 0 step, 0 way
- 1 step, 1 way
- 2 step, 2 ways (1,1 & 2)
- n step, (n-1) step's ways + (n-2) step's ways

So, the i's step ways denote as `d(i)`

.

`d(i) = d(i-1) + d(i-2)`

.

It's a fibonacci sequence. So, one way to direct calc:

```
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
import math
sqrt5 = math.sqrt(5)
return int(sqrt5 / 5 * (((1+sqrt5)/2)**(n+1) - ((1-sqrt5)/2)**(n+1)))
```

And iteration way:

```
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
x, y = 0, 1
while n:
y, x, n = x + y, y, n-1
return y
```

Continue...