What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Climbing Stairs Problem (With C++, Java and Python Code)

  • Jul 30, 2022
  • 7 Minutes Read
Climbing Stairs Problem (With C++, Java and Python Code)

In interviews and coding contests, indirect questions will be asked about the known concepts. In this article, we are going to discuss the leetcode problem of Climbing stairs. The problem might seem new but the logic is quite familiar even for the beginner. After reading the problem statement try to find the logic to solve this problem.

Problem statement

Let us consider you are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. We have to find how many distinct ways can you climb to the top.

Sample Input: n = 3
Sample Output: 3
(Way 1: 1->1->1, Way 2: 2->1, Way 3: 1->2)

Solution for Climbing Stairs Problem

Before we discuss the solution to this problem, let's discuss about dynamic programming.

What is dynamic programming?

Dynamic programming is a technique that divides the problem into parts, finds a solution at each stage, and stores it for future use. It is used to get an optimized solution with the concept of reusing the stored solutions of the sub-parts. The primary use of dynamic programming is to reduce time complexity. We can solve recursive problems with dynamic programming. It will reduce the time complexity from exponential to linear. Let's try to solve this climbing stairs problem with the help of dynamic programming.

Algorithm

The algorithm for Climbing stairs is exactly similar to the Fibonacci series.

  1. Let n be the number of stairs. If n <=0, then the number of ways to climb the staircase should be zero.
  2.  If n == 1, then there is only way to climb the stair.
  3. For the numbers greater than 1, we can simply find the solution by adding previous steps i.e., dp[n-1] + dp[n-2]. Create a new array and store the output at each step.
  4. Then finally return the last value in the array as the output.

Example

Let us consider the value of n is 3. There are 3 ways to reach the top. We use a dynamic programming approach for this problem. We create a new array of steps that store the value at each step. Let us first initialize steps[0] = 1 and steps[1] = 1, then to find steps[2] we have to add previous two values i.e., steps[0] + steps[1] which is 1+1 = 2.

Then to find steps[3] we have to add previous two values i.e., steps[1] + steps[2] which is 1+2 = 3. Now we know that steps[n] is the final output, hence steps[3] value i.e 3 is the required number of ways to climb the stairs. The explanation is illustrated in the following diagram.

Example of climbing stairs problem with 3 ways

Java Code for Climbing Stairs Problem

class Solution {
 public static int climbStairs(int n) {
  if(n<=0){
   return 0;
  }
  else if (n == 1) {
   return 1;
  }
  else{
   int[] steps = new int[n + 1];
   steps[0] = 1;
   steps[1] = 1;
   for (int i = 2; i <= n; i++) {
   steps[i] = steps[i - 2] + steps[i - 1];
   }
  }
 return steps[n];
 }
 public static void main(String[] args) {
  int n=3;
  System.out.println(climbStairs(n));
 }
}

 

Output

3

 

C++ Code for Climbing Stairs Problem

#include
using namespace std;
int climbStairs(int n) {
 if(n<=0){
  return 0;
 }
 else if (n <= 1) {
  return 1;
 }
 else{
  int steps[n+1];
  steps[0] = 1;
  steps[1] = 1;
  for (int i = 2; i <= n; i++) {
   steps[i] = steps[i - 2] + steps[i - 1];
  }
 }
 return steps[n];
}
int main(){
 int n=3;
 cout<<climbStairs(n);
 return 0;
}

 

Output

3

 

Python Code for Climbing Stairs Problem

def climbStairs(n):
 steps = []
 steps.append(1)
 steps.append(2)
 for i in range(2, n):
  steps.append(f[i - 1] + f[i - 2])
 return steps[n - 1]
n=3
print(climbStairs(n))

 

Output

3

 

Time complexity

We are iterating through a single loop to find a number of ways to climb the stairs. Hence the time complexity will be O(n), where n is the number of stairs.

Space complexity

In this approach of storing the values using dynamic programming, we are creating a new array. Hence the space complexity for this solution will be O(n), where n is the number of stairs.

Conclusion

Dynamic programming is an important concept to be covered for any interview or competitive programming. We can also solve this problem with a recursive approach but dynamic programming is much more efficient compared to recursion. There are many ways you can try to solve this problem so you will have a good understanding of the concepts.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Keerthana Buvaneshwaran
I'm Keerthana Buvaneshwaran, a computer science engineering student who loves to write technical content as well. I'm always curious to explore and gain knowledge of new technologies. I'm grateful to share my knowledge through my writing which will help others to develop their skills.