Climbing Stairs — Day 64(Python)

Image for post
Image for post
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:

Example 2:

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.

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

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

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.

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