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. step + 1 step
2. steps

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top.
1. step + 1 step + 1 step
2. step + 2 steps
3. 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 = memo =1

class Solution3:

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

memo = 1
memo = 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