### 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...