Climbing Stairs Problem

Problem Statement

Given a staircase of N steps you can either climb 1 or 2 steps at a given time. The task is to return the count of distinct ways to climb to the top.
Note: The order of the steps taken matters.

Examples:

Input: N = 3
Output: 3
Explanation:

There are three distinct ways of climbing a staircase of 3 steps :

Input:  N = 2
Output: 2
Explanation:

There are two distinct ways of climbing a staircase of 3 steps :

Brute Force (Recursive) Approach

The approach is to consider all possible combination steps i.e. 1 and 2, at every step. To reach the Nth stair, one can jump from either (N – 1)th or from (N – 2)th stair. Hence, for each step, total ways would be the summation of (N – 1)th stair + (N – 2)th stair.

The recursive function would be:

ClimbStairs(N) = ClimbStairs(N – 1) + ClimbStairs(N – 2).

If we observe carefully, the expression is nothing but the Fibonacci Sequence.

SampleRecursive Tree for N = 5:

Algorithm:

• If N < 2, return 1. This is the termination condition for the function.
• Else, find the summation of ClimbStairs(N – 1) + ClimbStairs(N – 2).

C++ Implementation of Recursive Approach

int climbStairs(int N)
{
    if ( N < 2 )
        return 1;
    else
        return climbStairs(N-1) + climbStairs(N-2);
}

Java Implementation of Recursive Approach

 static int climbStairs(int N){
    if ( N < 2 )
        return 1;
    else
        return climbStairs(N-1) + climbStairs(N-2);
}

Python Implementation of Recursive Approach

def climbStairs(N):
    if N < 2 :
        return 1
    else:
        return climbStairs(N-1) + climbStairs(N-2)

Bottom-up Approach

In the above approach, observe the recursion tree. It can be clearly seen that some of the subproblems are repeating. Hence, it is unnecessary to calculate those again and again. Therefore, we can store the result of those subproblems and retrieve the solution of those in O(1) time.

Since the problem contains an optimal substructure and has overlapping subproblems, it can be solved using dynamic programming.

One can reach the ith step in one of the two ways :

1. Take one step from (i – 1)th step.
2. Take two steps from (i – 2)th step.

Algorithm

• Initialise a dp[] array of size N + 1.
• Assign dp[0] and dp[1] to 1.
• Iterate a loop from 2 till N and for each iteration:
  • dp[i] = dp[i – 1] + dp[i – 2]
• Return the value of dp[N].

C++ Implementation of DP Approach

int climbStairs(int N)
{
    int dp[N+1];
    dp[0] = 1
    dp[1] = 1
    for (i = 2; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[N];
}

Java Implementation of DP Approach

 static int climbStairs(int N)
{
    int dp[] = new int[N+1];
    dp[0] = 1
    dp[1] = 1
    for (i = 2; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[N];
}

Python Implementation of DP Approach

def climbStairs(N):
    dp = [0]*(N + 1)
    dp[0] = 1
    dp[1] = 1
        
    for i in range(2, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
            
    return dp[N]

Fibonacci Number Approach

In the above approach, the dp array is just storing the value of the previous two steps from the current ith position i.e. (i – 1)th and (i – 2)th position.

The space complexity can be further optimized, since we just have to find an Nth number of the Fibonacci series having 1 and 2 as their first and second term respectively, i.e. Fib(1) = 1 and Fib(2) = 2.

Algorithm

• Initialise two variables first = 1 and second = 2.
• Iterate a loop from i = 3 till i = N and for each step:
  • Initialise a variable third = first + second
  • first = second
  • second = third
• Return second after the iteration ends.

C++ Implementation

int climbStairs(int N)
{
    if (N == 1) {
            return 1;
    }
    int first = 1;
    int second = 2;
    for (int i = 3; i <= N; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    return second;
}

Java Implementation

 public int climbStairs(int N) {
        if (N == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= N; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }

Python Implementation

def climbStairs(N):
    if N == 1:
       return 1
    first = 1;
    second = 2;
    for i in range(3, N + 1):
        third = first + second;
        first = second;
        second = third;
 
    return second;

Practice Question

• Stairs Problem

FAQs

Q.1: What is the most efficient approach to solving the Climbing stairs problem?

Ans: The approach to finding the Nth Fibonacci number is the most efficient since its time complexity is O(N) and space complexity is O(1).

Q.2: How to solve this problem if it’s given that one can climb up to K steps at a time?

Ans: If one can climb K steps at a time, try to find all possible combinations from each step from 1 to K.

The recursive function would be :
climbStairs(N, K) = climbStairs(N – 1, K) + climbStairs(N – 2, K) + … + climbStairs(N – K , K).