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.