Ready to solve a popular DSA problem? We are going to learn this problem called “climbing stairs”.

## 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.

## Visualise This Problem

At any step, we have only two choices:

a. We can take one step.

b. We can take two steps.

In other words, If 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 details.

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 step 1, which is by taking one step.Now, let’s move on to the remaining steps:

### 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.

## 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.

## Solution

The man with the solution key is here.

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) I 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.

Thank you People illustrations by Storyset