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

Note: Given n will be a positive integer.

Example:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


Although the above answer is in lexicographical order, your answer could be in any order you want.

## Thought Process

The problem can be solved in a recursive way:

## White Board

Below is the white board:

## Code

class Solution:

def climbstairs(self, n):
if n == 1:
return 1
if n == 2:
return 2

return self.climbstairs(n-1) + self.climbstairs(n-2)

def test():
cs = Solution().climbstairs(5)
print(cs)

test()

8


## Complexity

• Time complexity is O(2**n), which will TLE (Time Limit Exceeded)

## Optimization

One way to improve this is via memoization.

class Solution2:

def climbstairs_m(self, n):
memo = [-1] * (n+1)

if n == 1:
memo[n] = 1

if n == 2:
memo[n] = 2

if memo[n] == -1:
memo[n] = self.climbstairs_m(n-1) + self.climbstairs_m(n-2)

return memo[n]

def test():
csm = Solution2().climbstairs_m(5)
print(csm)

test()

8


The above two solutions will TLE. Another way to optimize is via dynamic programming. Now think about the base case, if there are 0 stairs, there is 1 way: don’t move; if there are 1 stails there’s 1 way. so memo[0] = memo[1] =1

class Solution3:

def climbStairs_dp(self, n):
memo = [-1] * (n+1)

memo[0] = 1
memo[1] = 1

for i in range(2,n+1):
memo[i] = memo[i-2] + memo[i-1]

return memo[n]

def test():
csdp=Solution3().climbStairs_dp(5)
print(csdp)

test()

8


Time and space complexities are both O(n) for dynamic programming version.