The climbing stairs LeetCode problem is a common interview problem that embodies an example where a coder has to combine a set of decisions under certain constraints. The problem demands us to determine the number of ways we can climb a staircase with

Let’s look at the problem in detail. The problem creates a scenario of having to climb a staircase. This staircase has total of * steps.* We can take a single step or two at once to reach the top. The problem demands us to calculate the total number of unique ways to reach the top.

**Constraints:**

$1 \leq n \leq 10^3$ Climb one or two stairs at once

Inspect the slides below to better visualize the problem statement.

One step

Now that we’ve understood the problem, let’s check our knowledge by finding the total ways to reach the top of the example below:

If we observe the above examples, we’ll notice a strange pattern: the total number of ways to get to the top is equal to the sum of the previous two consecutive ways to reach the top. This is demonstrated with the following illustration:

One step

Does it sound like the Fibonacci series? Well, it is.

Here’s how we determine the number of ways to reach the top with

We loop over the total number of single steps needed to reach the top:

${n-1}$ *.*We then sum the previous two terms: ways taken to reach the top when the step count is

${n-1}$ and${n-2}$ . We store the sum in the variable`current_number_of_ways`

. The number of ways for${n-1}$ `consecutive_1`

and that for${n-2}$ is stored in`consecutive_2`

.Next, we replace/update the value of

`consecutive_2`

with`consecutive_1`

.Lastly, we replace/update the value of

`consecutive_1`

with`current_number_of_ways`

.

Let’s look at the code for the above algorithm that implements the Fibonacci series to calculate the total number of ways to reach the top.

def educatives_ways_to_reach_on_top(n):# Stores the total ways to climb n - 1 stepsconsecutive_1 = 1# Stores the total ways to climb n - 2 stepsconsecutive_2 = 1# Loop over the total single steps needed to reach the top for n stepsfor _ in range(2, n + 1):# Current_number_of_ways stores the sum of the previous two termscurrent_number_of_ways = consecutive_1 + consecutive_2# Update the value of consecutive_2 to consecutive_1 and consecutive_1 to current_number_of_waysconsecutive_2 = consecutive_1consecutive_1 = current_number_of_ways# In the end, consecutive_1 will store the total steps to reach the top on n stairsprint(" Total number of ways to reach the top are : ", consecutive_1)# Test code: update the value of n = 1,2,3... and observe the result :)if __name__ == "__main__":n = 4educatives_ways_to_reach_on_top(n)

**Lines 1–6:**We define a function called`educatives_ways_to_reach_on_top()`

and pass the total number of steps in the staircase to it. Then, we initialize two variables`consecutive_1`

for`n – 1`

and`consecutive_2`

for`n – 2`

with the value`1`

.**Lines 9–14:**Next, we iterate over the total number of jumps needed to reach the top when there are`n`

steps. We store the sum of`consecutive_1`

and`consecutive_2`

in the variable`current_number_of_ways`

. After that, we update the values of`consecutive_2`

with`consecutive_1`

and`consecutive_1`

with`current_number_of_ways`

.**Lines 19–22:**This code section tests the function we defined above. We can pass it any value of`n`

.

It shouldn’t be surprising to know that the time complexity of this algorithm is, in fact, *for* loop:

The space complexity is

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS