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.

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.