Solving the Staircase Problem: How Many Ways Can You Climb?

A popular DSA problem asked by Adobe, Amazon and Yahoo

Jul 13, 2023

Problem Statement

You are faced with a staircase that has a certain number of steps, denoted by n. Each time, you can either climb 1 step or 2 steps. The goal is to figure out how many distinct ways you can reach the top of the staircase.

Do you want to take a few minutes to think about the possible approach before reading further?

Visualise This Problem

At any step, we have only two choices:

We can climb one step.
We can climb two steps.

In other words, if I am at step 4, I could have come to step 4 only from step 3 or from step 2. There is no other way.

Let’s understand in more detail.

Let’s consider an example where n = 4. We want to find the number of distinct ways to climb a staircase with 4 steps.

Step 0:

There is only one way to climb step 0, which is by not taking any steps.

Step 1:

Similarly, there is only one way to climb to step 1, which is by taking one step.

Step 2:

To reach step 2, we can either take two 1-step jumps or a single 2-step jump. Therefore, there are 2 distinct ways to reach step 2.

Step 3:

To reach step 3, we can either:

Start from step 2 and take a single 1-step jump.
Start from step 1 and take a single 2-step jump.

Therefore, there are 3 distinct ways to reach step 3.

Step 4:

To reach step 4, we can either:

Start from step 3 and take a single 1-step jump.
Start from step 2 and take a single 2-step jump.

Therefore, there are 5 distinct ways to reach step 4.

By analyzing this example, you can observe a pattern emerging. The number of distinct ways to reach a particular step is the sum of the distinct ways to reach the previous two steps.

This pattern continues for larger values of n as well. Using this observation, we can build a dynamic programming solution to calculate the number of distinct ways to climb to the top of the staircase for any given value of n.

This would be a good time to build further on this idea and solve the problem programmatically.

But why dynamic programming?

Overlapping subproblems

The problem can be divided into smaller subproblems, and the solution to the larger problem can be built by combining the solutions to these subproblems. Moreover, these subproblems often have overlapping substructures, meaning the same subproblem is solved multiple times

In the staircase problem, the number of ways to climb to a particular step depends on the number of ways to reach the previous two steps. This recursive relation indicates overlapping subproblems because the number of ways for a step is dependent on the number of ways for smaller steps (i-1 and i-2).

Optimal substructure

The optimal solution to the problem can be constructed from optimal solutions to its subproblems. In other words, the optimal solution to the problem exhibits optimal solutions to its smaller subproblems.

In the staircase problem, finding the number of distinct ways to climb to the top is based on the optimal solutions for smaller steps. By combining the optimal solutions for smaller steps, we can derive the optimal solution for the larger problem.

We can break it down into subproblems and build a solution from the bottom up. Let’s consider the base cases first:

If there are 0 steps, there is only 1 way to climb to the top (by not taking any steps).
If there is 1 step, there is only 1 way to climb to the top (by taking one step).

Now, let’s consider the general case. If we are at step i, we can reach it from either step i-1 (by taking one step) or step i-2 (by taking two steps). Therefore, the total number of distinct ways to reach step i is the sum of the number of ways to reach steps i-1 and i-2. Using this recursive relation, we can build our solution iteratively. We start with the base cases and compute the number of ways to reach each step up to n.

In this example, when n is 4, there are 5 distinct ways to climb to the top of the staircase: (1, 1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), and (2, 2).

We can write mathematically:

f(n) = 1,                    if n = 0 or n = 1
f(n) = f(n-1) + f(n-2),      if n > 1

Code

Java

class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        int count = distinctWays(n,0,memo);
        return count;
    }
    
    public int distinctWays(int n,int count, int memo[]){
        if(count > n)
            return 0;
        if(count == n)
            return 1;
        if(memo[count] > 0)
            return memo[count];
        int res =  distinctWays(n, count + 1, memo) + distinctWays(n, count + 2, memo);
        memo[count] = res;
        return res;
    }
}

Python

class Solution(object):
    def climbStairsHelper(self, n, memo):
        if n == 0 or n == 1:
            return 1

        if memo[n] != 0:
            return memo[n]

        memo[n] = self.climbStairsHelper(n - 1, memo) + self.climbStairsHelper(n - 2, memo)
        return memo[n]

    def climbStairs(self, n):
        memo = [0] * (n + 1)
        return self.climbStairsHelper(n, memo)

C++

class Solution {
  int climbStairsHelper(int n, std::vector < int > & memo) {
    if (n == 0 || n == 1) {
      return 1;
    }

    if (memo[n] != 0) {
      return memo[n];
    }

    memo[n] = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);
    return memo[n];
  }

  public: int climbStairs(int n) {
    std::vector < int > memo(n + 1, 0);
    return climbStairsHelper(n, memo);
  }
};

Conclusion

The best way to learn coding is to code (how non-trivial :P)

We would recommend that you attempt this problem on your own. We explored a beginner-friendly solution to the staircase problem using dynamic programming. By visualizing the staircase, breaking down the problem, and finding patterns, we were able to calculate the number of distinct ways to climb to the top. The dynamic programming approach helped us solve the problem efficiently and avoid redundant calculations.

Want more of such problems?

Explore the ‘Problem of the Day’. One problem each day that would help you get better at DSA and problem-solving. Check it out here: https://skillcaptain.app/

Resources

StorySet for the illustrations

SkillCaptain - Everything Tech

Discussion about this post