Climbing Stairs — Day 64(Python)

Photo by Serhat Beyazkaya on Unsplash

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:

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

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store