Climbing Stairs — Day 64(Python)

Annamariya Tharayil

Jan 29·3 min read

Today’s question is an easy tagged question from leetcode. Let us look into the problem statement.

70. Climbing Stairs

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

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

Example 1:

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

Example 2:

Input: n = 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

Constraints:

• 1 <= n <= 45

We can try to solve this problem using recursion. Before we start with recursion, we need to identify the base condition.

What is the minimum valid input for this problem? The problem statement says you can take either 1 step or 2 steps at a time. Hence the smallest valid input is 1 and 2. Let us define the base condition.

if n == 1:
   return 1
elif n == 2:
   return 2

Next, we have to make choices. We can either take 1 step or take 2 steps at a time.

else:
    return self.climbStairs(n-1) + self.climbStairs(n-2)

That's it. We have solved the problem using recursion. Let us look into the complete code snippet.

class ClimbStairsCounter:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

Complexity analysis.

Time Complexity

At each point, we have two choices to make, either take 1 step or take 2 steps. Hence the time complexity is O(2^N).

Space Complexity.

At each point, we have two choices to make, either take 1 step or take 2 steps. Since we are using recursion, internally we are creating a stack of size 2^N. Hence we space complexity is O(2^N).

If we run this code in leetcode, we will get a time limit exceeded error.

Let us optimize this code using dynamic programming.

There is one entity that keeps changing during each call, which is the number of stairs. Hence we will be creating a 1-D array of size of the number of stairs.

We will be initializing the first 2 cells with 1 and 2. This is equivalent to the base condition in the recursive approach.

Next, we will be filling the values, based on the previous two cells. Let us look into the code snippet.

class ClimbStairsCounter:
    def climbStairs(self, n: int) -> int:
        dp = [0 for i in range(n)]
        dp[0] = 1
        if n == 1:
            return dp[0]
        dp[1] = 2
        if n == 2:
            return dp[1]
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

Complexity analysis.

Time Complexity

We are traversing through a 1D array of size N. Hence the time complexity is O(N).

Space Complexity.

We are creating a 1D array of size N. Hence the space complexity is O(N).