How to climb stairs

Given a staircase with a number of steps. Count how many distinct ways can you climb the stairs. In one step, you can climb one or two steps

 

Example 1

Input: 1

Output: 1

Explanation: One way to go up the stairs

Example 2

Input: 2

Output: 2

Explanation: Two ways climb the stairs:

• Climbing by one step
• Climbing by two steps

We need to find out how many ways we could climb the stairs. Let's assume the stairs have n steps, and we are already on the top.

 

 

We could reach the top from n-1 step and n-2. And the number of ways how to achieve n would be the number of ways to achieve n-1 plus the number of ways to achieve n-2.

 

 

Now we can write down the resulting formula for calculating the number of ways to climb the stairs F(n) = F(n-1) + F(n-2)

Before writing the code, let's see two base scenarios. The stairs have 1 and 2 steps.

• if the stairs have only one step, there's only one way to climb
• if the stairs have two steps, there are two ways to climb stairs:
  • climb stairs in two steps ( one by one)
  • climb to the top in one step

Recursive approach

  public int ClimbStairs(int steps)
  {
      if(steps <= 2)
      {
          return steps;
      }
      
      return ClimbStairs(steps - 1) + ClimbStairs(steps - 2);
  }

The recursive version is pretty simple. The code is exactly like our formula. There is only one downside, the time complexity is really bad: O(2^n)

Iterative approach

The recursive approach works only for small numbers because of time complexity. The same can be done using the bottom-up approach of dynamic programming. The idea is to reuse already calculated values and not count from scratch.

  public int ClimbStairs(int steps)
  {
      int step0 = 1;
      int step1 = 1;
  
      if (steps <= 1)
      {
          return 1;
      }
  
      for (int i = 2; i < steps; i++)
      {
          int dummy = step0 + step1;
  
          step0 = step1;
          step1 = dummy;
      }
  
      return step0 + step1;
  }

The code is a bit less readable compared to the recursive approach, but the time complexity is O(n) which is a huge improvement compared to O(2^n).